Conference Papers / Δημοσιεύσεις σε Συνέδρια

In this work we experimentally study the min order Radiocoloring problem (RCP) on Chordal, Split and Permutation graphs, which are three basic families of perfect graphs. This problem asks to find an assignment using the minimum number of colors to the vertices of a given graph G, so that each pair of vertices which are at distance at most two apart in G have different colors. RCP is an NP-Complete problem on chordal and split graphs [4]. For each of the three families, there are upper bounds or/and approximation algorithms known for minimum number of colors needed to radiocolor such a graph [4, 10]. We design and implement radiocoloring heuristics for graphs of above families, which are based on the greedy heuristic. Also, for each one of the above families, we investigate whether there exists graph instances requiring a number of colors in order to be radiocolored, close to the best known upper bound for the family. Towards this goal, we present a number generators that produce graphs of the above families that require either (i) a large number of colors (compared to the best upper bound), in order to be radiocolored, called "extremal" graphs or (ii) a small number of colors, called "non-eztrema/ "instances. The experimental evaluation showed that random generated graph instances are in the most of the cases "non-extremal" graphs. Also, that greedy like heuristics performs very well in the most of the cases, especially for "non-extremal" graphs.

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 Lspecifications 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 Lspecified 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, G2, where G2 has the same vertex set as G and there is an edge between any two vertices of G2 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].

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 [21,22], 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 recognized in polynomial time. 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. 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 asymptotic 10/3- 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 5/3 asymptotically ([27,28]).