0000000000010876

AUTHOR

Gerhard Weißenfels

showing 2 related works from this author

On the chromatic number of disk graphs

1998

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.

Clique-sumComputer Networks and CommunicationsTrapezoid graph1-planar graphMetric dimensionCombinatoricsIndifference graphPathwidthHardware and ArchitectureChordal graphMaximal independent setSoftwareMathematicsofComputing_DISCRETEMATHEMATICSInformation SystemsMathematicsNetworks
researchProduct

On Coloring Unit Disk Graphs

1998

In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.

Discrete mathematicsGeneral Computer ScienceApplied MathematicsAstrophysics::Cosmology and Extragalactic AstrophysicsComplete coloring1-planar graphComputer Science ApplicationsBrooks' theoremCombinatoricsGreedy coloringIndifference graphEdge coloringChordal graphHigh Energy Physics::ExperimentGraph coloringMathematicsAlgorithmica
researchProduct