Approximation Algorithms for Domatic Partitions of Unit Disk Graphs

DOI10.1007/978-3-642-03685-9_24MaRDI QIDQ3638887zbMATH OpenOpenAlexFDO

Authors Saurav Pandit, Sriram Pemmaraju, Kasturi Varadarajan

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_24

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
• Graph-Theoretic Concepts in Computer Science
• Approximation Algorithms for Some Graph Partitioning Problems
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Linear-time approximation algorithms for unit disk graphs
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• The algorithmic complexity of \(k\)-domatic partition of graphs
• A class of bounded approximation algorithms for graph partitioning
• scientific article; zbMATH DE number 4011955

Cited in

(10)

• A weakly robust PTAS for minimum clique partition in unit disk graphs
• Distributed Approximation Algorithms in Unit-Disk Graphs
• Distributed Approximations for Packing in Unit-Disk Graphs
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Optimally decomposing coverings with translates of a convex polygon
• Approximating 2-cliques in unit disk graphs
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• The subinterval cover problem
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS

This page was built for publication: Approximation Algorithms for Domatic Partitions of Unit Disk Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638887)