Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Glimpse at Paul G. Spirakis Read chapter Read first chapter

2015 | OriginalPaper | Chapter

On Radiocoloring Hierarchically Specified Planar Graphs: \(\mathcal{PSPACE}\)-completeness and Approximations

Authors : Maria Andreou, Dimitris Fotakis, Vicky Papadopoulou Lesta, Sotiris Nikoletseas, Paul Spirakis

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 [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 \(\mathcal{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]).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On the Implementation of Combinatorial Algorithms for the Linear Exchange Market
next chapter Performance Evaluation of Routing Mechanisms for VANETs in Urban Areas
Literature
1.
2.
Andreou, M.I., Fotakis, D.A., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: On radiocoloring hierarchically specified planar graphs: \({{\cal {P}SPACE}}\)-Completeness and approximations. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 81–92. Springer, Heidelberg (2002) CrossRef
3.
4.
Bienstoc, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica 5, 93–109 (1990)MathSciNetCrossRefMATH
5.
Bodlaender, H.L.: Planar graphs with bounded treewidth. TR RUU-CS-88-14, Department of Computer Science, University of Utrecht, The Netherlands, March 1988
6.
Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: \(\lambda \)-Coloring of Graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 395–406. Springer, Heidelberg (2000) CrossRef
7.
Borodin, O.V., Broersma, H.J., Glebov, A., van den Heuvel, J.: Stars and bunches in planar graphs. Part II: General planar graphs and colourings. CDAM Research Report 2002–2005 (2002)
8.
Calamoneri, T., Petreschi, R.: \(L(2,1)\)-Coloring Matrogenic Graphs. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 236–247. Springer, Heidelberg (2002) CrossRef
9.
Fotakis, D.A., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: NP-completeness results and efficient approximations for radiocoloring in planar graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 363–372. Springer, Heidelberg (2000) CrossRef
10.
Fotakis, D., Nikoletseas, S., Papadopoulou, V.G., Spirakis, P.G.: Radiocoloring in planar graphs: complexity and approximations. Theoret. Comput. Sci. 340, 514–538 (2005). ElsevierMathSciNetCrossRefMATH
11.
Fotakis, D., Pantziou, G., Pentaris, G., Spirakis, P.: Frequency assignment in mobile and radio networks. In: Networks in Distributed Computing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 45, pp. 73–90. American Mathematical Society, Providence (1999)
12.
13.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the Theory of NP-completeness. W.H./Freeman and Company (1979)
14.
Griggs, J., Liu, D.: Minimum span channel assignments. Recent Advances in Radio Channel Assignments, Invited Minisymposium, Discrete Mathematics (1998)
15.
Griggs, J.R., Yeh, R.K.: Labeling graphs with a condition at distance 2. SIAM J. Disc. Math. 5, 586–595 (1992)CrossRefMATH
16.
Jonas, T.K.: Graph Coloring Analogues With a Condition at Distance Two: L(2, 1)- Labelings and List \(\lambda \)-Labelings. Ph.D. thesis, Department of Mathematics, University of South Carolina, Columbia, SC (1993)
17.
Harary, F.: Private communication to Paul Spirakis
18.
19.
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 468–477. Springer, Heidelberg (1994)
20.
Krumke, Marathe, M.V., Ravi, S.S.: Approximation algorithms for channel assignment in radio networks. In: DIALM for Mobility, 2nd International Workshop on Discrete Algorithms and methods for Mobile Computing and Communications, Dallas, Texas (1998)
21.
22.
Lengauer, T., Wagner, K.W.: Correlation between the complexities of the of hierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63–93 (1992)CrossRefMATH
23.
Marathe, M.V., Hunt III, H.B., Stearns, R.E., Radhakrishnan, V.: Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. In: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC), pp. 468–478, May 1994. A complete version appears in SIAM Journal on Computing 27(5), 1237–1261 (1998)
24.
Marathe, H., Hunt III, H., Stearns, R., Radhakrishnan, V.: Complexity of hierachically and 1-dimensioned periodically specified problems. In: Theory and Applications, DIMACS Workshop on Satisfiability Problem (1996)
25.
Marathe, M.V., Radhakrishnan, V., Hunt III, H.B., Ravi, S.S.: Hierarchically specified unit disk graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 21–32. Springer, Heidelberg (1994). Journal version appears in Theoretical Computer Science, 174(1-2), pp. 23-65, March 1997 CrossRef
26.
McCormick, S.T.: Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Technical Report SOL 81–22, Department of Operations Research, Standford University (1981)
27.
Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph. J. Combin. Theory Ser. B 94, 189–213 (2005)MathSciNetCrossRefMATH
28.
Molloy, M., Salavatipour, M.R.: Frequency channel assignment on planar networks. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 736–747. Springer, Heidelberg (2002) CrossRef
29.
Ramanathan,S., Loyd, E.R.: The complexity of distance2-coloring. In: 4th International Conference of Computing and information, pp. 71–74 (1992)
30.
31.
Zhou, X., Kanari, Y., Nishizeki, T.: Generalized vertex-coloring of partial k-trees. IEICE Trans. Foundamentals EXX-A(1) (2000)
Metadata
Title
On Radiocoloring Hierarchically Specified Planar Graphs: -completeness and Approximations
Authors
Maria Andreou
Dimitris Fotakis
Vicky Papadopoulou Lesta
Sotiris Nikoletseas
Paul Spirakis
Copyright Year
2015
Book
Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-24024-4_8

Premium Partner

    Image Credits