Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

DOI10.1016/j.jda.2005.12.007zbMath1125.90011OpenAlexW2061144276WikidataQ59818659 ScholiaQ59818659MaRDI QIDQ849634

Dimitris Fotakis, Vicky G. Papadopoulou, Sotiris E. Nikoletseas, Paul G. Spirakis

Publication date: 31 October 2006

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.12.007

zbMATH Keywords

computational complexitycoloringapproximation algorithmsperiodic graphsfrequency assignmentradio networks

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Cites Work

• Planar graphs: Theory and algorithms
• Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Minimum Cost Paths in Periodic Graphs
• On Colorings of Squares of Outerplanar Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies