A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
DOI10.1051/ita/2011106zbMath1228.05224OpenAlexW2090708733MaRDI QIDQ3095042
T. O. Ferreira, Márcia R. Cerioli, Fábio Protti, Luérbio Faria
Publication date: 28 October 2011
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2011__45_3_331_0/
Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (8)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The minimum broadcast time problem for several processor networks
- On sum coloring and sum multi-coloring for restricted families of graphs
- Unit disk graphs
- On some problems of elementary and combinatorial geometry
- The complexity of comparability graph recognition and coloring
- Unit disk graph recognition is NP-hard
- Good Quality Virtual Realization of Unit Ball Graphs
- A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
- Universality considerations in VLSI circuits
- Planar Formulae and Their Uses
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
This page was built for publication: A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation