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 our problem, channels assigned to adjacent vertices must be at least 2 apart, while channels assigned to vertices at distance 2 must be different. An exact linear time algorithm is provided for the class of threshold graphs. For matrogenic and matroidal graphs approximate algorithms are given. Consequently, previously known results concerning subclasses of cographs, split graphs and graphs with diameter 2 are improved. (c) 2006 Elsevier B.V. All rights reserved.
lambda-coloring matrogenic graphs / Calamoneri, Tiziana; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 154:(2006), pp. 2445-2457. [10.1016/j.dam.2006.03.036]
lambda-coloring matrogenic graphs
CALAMONERI, Tiziana;PETRESCHI, Rossella
2006
Abstract
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 our problem, channels assigned to adjacent vertices must be at least 2 apart, while channels assigned to vertices at distance 2 must be different. An exact linear time algorithm is provided for the class of threshold graphs. For matrogenic and matroidal graphs approximate algorithms are given. Consequently, previously known results concerning subclasses of cographs, split graphs and graphs with diameter 2 are improved. (c) 2006 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
