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/

zbMATH Keywords

independent setapproximation algorithmsclique partitionunit disk graphspenny graphsunit coin graphs

Mathematics Subject Classification ID

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)

Space-efficient algorithms for reachability in directed geometric graphs ⋮ Harmonic functions of polynomial growth on infinite penny graphs ⋮ On arrangements of orthogonal circles ⋮ Covering a Graph with Clubs ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ Discrete harmonic functions on infinite penny graphs ⋮ On the tractability of covering a graph with 2-clubs ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction*

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