Advertisement
Published in:
2006 | OriginalPaper | Chapter
Generalized Powers of Graphs and Their Algorithmic Use
Authors : Andreas Brandstädt, Feodor F. Dragan, Yang Xiang, Chenyu Yan
Published in: Algorithm Theory – SWAT 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Motivated by the frequency assignment problem in heterogeneous multihop radio networks, where different radio stations may have different transmission ranges, we introduce two new types of coloring of graphs, which generalize the well-known Distance-k-Coloring. Let
G
=(
V
,
E
) be a graph modeling a radio network, and assume that each vertex
v
of
G
has its own transmission radius
r
(
v
), a non-negative integer. We define
r-coloring
(
r
+
-coloring
) of
G
as an assignment Φ:
V
↦{0,1,2,...} of colors to vertices such that Φ(
u
)=Φ(
v
) implies
d
G
(
u
,
v
)>
r
(
v
)+
r
(
u
) (
d
G
(
u
,
v
)>
r
(
v
)+
r
(
u
)+1, respectively). The
r-Coloring problem
(
the r
+
-Coloring problem
) asks for a given graph
G
and a radius-function
r
:
V
↦
N
∪{0}, to find an
r
-coloring (an
r
+
-coloring, respectively) of
G
with minimum number of colors. Using a new notion of generalized powers of graphs, we investigate the complexity of the
r
-Coloring and
r
+
-Coloring problems on several families of graphs.