hide
Free keywords:
-
Abstract:
Hierarchical specifications of graphs have been widely used in many important
applications, such as VLSI design, parallel programming and software
engineering. A well known hierarchical specification model, considered in this
work, is that of Lengauer [9, 10] referred to as L-specifications. In this
paper we discuss a restriction on the L-specifications resulting to graphs
which we call Well-Separated (WS). This class is characterized by a polynomial
time (to the size of the specification of the graph) testable combinatorial
property.
In this work we study the Radiocoloring Problem (RCP) on WS L-specified
hierarchical planar graphs. The optimization version of RCP studied here,
consists in assigning colors to the vertices of a graph, such that any two
vertices of distance at most two get different colors. The objective here is to
minimize the number of colors used. This problem is equivalent to the problem
of vertex coloring the square of a graph $G$, $G^2$, where $G^2$ has the same
vertex set as $G$ and there is an edge between any two vertices of $G^2$ if
their distance in $G$ is at most 2.
We first show that RCP is PSPACE-complete for WS L-specified hierarchical
planar graphs. Second, we present a polynomial time 3-approximation algorithm
as well as a more efficient 4-approximation algorithm for RCP on graphs of this
class.
We note that, the best currently known approximation ratio for the RCP on
ordinary (non-hierarchical) planar graphs of general degree is 2 ([6, 1]). Note
also that the only known results on any kind of coloring problems have been
shown for another special kind of hierarchical graphs (unit disk graphs)
achieving a 6-approximation solution [13].
