On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
DOI10.1007/978-3-319-24024-4_8zbMath1331.68096OpenAlexW1952683795MaRDI QIDQ3464470
Vicky Papadopoulou Lesta, Maria I. Andreou, Dimitris Fotakis, Sotiris E. Nikoletseas, Paul G. Spirakis
Publication date: 27 January 2016
Published in: Algorithms, Probability, Networks, and Games (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-24024-4_8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of embedding planar graphs to minimize certain distance measures
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Some simplified NP-complete graph problems
- Hierarchically specified unit disk graphs
- A bound on the chromatic number of the square of a planar graph
- Radiocoloring in planar graphs: Complexity and approximations
- Labelling Graphs with a Condition at Distance 2
- Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
- Labeling Chordal Graphs: Distance Two Condition
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Coloring Powers of Planar Graphs
- Hierarchical planarity testing algorithms
- Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
- Coloring the square of a planar graph
- Models and approximation algorithms for channel assignment in radio networks
This page was built for publication: On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
