Radiocoloring in planar graphs: Complexity and approximations
From MaRDI portal
Publication:2566036
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
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
