Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Andreou, Maria
Fotakis, Dimitris
Nikoletseas, Sotiris
Papadopoulou, Vicky
Spirakis, Paul G.

dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Andreou, Maria
Nikoletseas, Sotiris
Papadopoulou, Vicky
Spirakis, Paul G.

Editor(s):

Diks, Krzysztof
Rytter, Wojciech

dblp
dblp

Not MPII Editor(s):

Diks, Krzysztof
Rytter, Wojciech

BibTeX cite key*:

AFNPS02

Title, Booktitle

Title*:

On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations


mfcs02.ps (314.91 KB)

Booktitle*:

Mathematical Foundations of Computer Science 2002 : 27th International Symposium, MFCS 2002

Event, URLs

URL of the conference:

http://mfcs.mimuw.edu.pl:9080/

URL for downloading the paper:


Event Address*:

Warsaw, Poland

Language:

English

Event Date*
(no longer used):

-- August 26-30, 2002

Organization:


Event Start Date:

26 August 2002

Event End Date:

30 August 2002

Publisher

Name*:

Springer

URL:

http://www.springer.de

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

2420

Number:


Month:

August

Pages:

81-92

Year*:

2002

VG Wort Pages:


ISBN/ISSN:

3-540-44040-2

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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].



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{AFNPS02,
AUTHOR = {Andreou, Maria and Fotakis, Dimitris and Nikoletseas, Sotiris and Papadopoulou, Vicky and Spirakis, Paul G.},
EDITOR = {Diks, Krzysztof and Rytter, Wojciech},
TITLE = {On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations},
BOOKTITLE = {Mathematical Foundations of Computer Science 2002 : 27th International Symposium, MFCS 2002},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2420},
PAGES = {81--92},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Warsaw, Poland},
MONTH = {August},
ISBN = {3-540-44040-2},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Dimitris Fotakis
Created
11/21/2002 04:31:14 PM
Revisions
12.
11.
10.
9.
8.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
01/20/2009 07:09:41 PM
28.08.2003 15:56:15
28.08.2003 15:38:40
26.08.2003 15:05:03
20.06.2003 15:43:39
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
mfcs02.ps