scientific article; zbMATH DE number 2230206

zbMath1075.05571MaRDI QIDQ5708492

Fábio Protti, Márcia R. Cerioli, T. O. Ferreira, Luérbio Faria

Publication date: 18 November 2005

Full work available at URL: http://www.sciencedirect.com/science/journal/15710653

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Approximation algorithms for intersection graphs ⋮ Minimum clique partition in unit disk graphs ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ Unnamed Item ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ On the chromatic number of disjointness graphs of curves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• Universality considerations in VLSI circuits
• 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: