Radiocoloring in planar graphs: Complexity and approximations

DOI10.1016/j.tcs.2005.03.013zbMath1077.68072OpenAlexW2027460314WikidataQ59818713 ScholiaQ59818713MaRDI QIDQ2566036

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

Publication date: 22 September 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.013

zbMATH Keywords

computational complexitytransmittersFrequency Assignment Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

OPTIMAL RADIOCOLORING OF TREES ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ A Glimpse at Paul G. Spirakis ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\) ⋮ \(L(p,q)\)-labeling and integer tension of a graph embedded on torus ⋮ Bounds on vertex colorings with restrictions on the union of color classes

Cites Work

• Probabilistic methods for algorithmic discrete mathematics
• Zero knowledge and the chromatic number
• Drawing Graphs in the Plane with High Resolution
• Planar Formulae and Their Uses
• A new approach to the minimum cut problem
• Algorithms for Square Roots of Graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Radiocoloring in planar graphs: Complexity and approximations