2002 | OriginalPaper | Buchkapitel
L(2, 1)-Coloring Matrogenic Graphs
(Extended Abstract)
verfasst von : Tiziana Calamoneri, Rossella Petreschi
Erschienen in: LATIN 2002: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In this problem, channels assigned to adjacent vertices must be at least two apart, while the same channel can be reused for vertices whose distance is at least three. Linear time algorithms are provided for matrogenic graphs and, in particular, for two specific subclasses: threshold graphs and split matrogenic graphs. For the first one of these classes the algorithm is exact, while for the other ones it approximates the optimal solution. Consequently, improvements on previously known results concerning subclasses of cographs, split graphs and graphs with diameter two are achieved.