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

DOI10.1016/J.JDA.2005.12.007zbMATH Open1125.90011OpenAlexW2061144276WikidataQ59818659 ScholiaQ59818659MaRDI QIDQ849634FDOQ849634

Authors: Dimitris Fotakis, Vicky Papadopoulou, Sotiris E. Nikoletseas, P. 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

Recommendations

• scientific article; zbMATH DE number 1953096
• Radiocoloring in planar graphs: Complexity and approximations
• scientific article; zbMATH DE number 1929928
• scientific article; zbMATH DE number 1759423
• On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
• scientific article; zbMATH DE number 1819633
• A survey on radio \(k\)-colorings of graphs
• A graph radio \(k\)-coloring algorithm
• A new graph radio \(k\)-coloring algorithm
• scientific article; zbMATH DE number 1862255

zbMATH Keywords

computational complexityapproximation algorithmscoloringfrequency assignmentradio networksperiodic graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum Cost Paths in Periodic Graphs
• Planar graphs: Theory and algorithms
• Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
• On colorings of squares of outerplanar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Experimental and Efficient Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q849634)