Improved algorithm for maximum independent set on unit disk graph

DOI10.1007/978-3-319-29221-2_18MaRDI QIDQ2795948zbMATH OpenOpenAlexFDO

Authors Ramesh K. Jallu, Gautam K. Das

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-29221-2_18

zbMATH Keywords

approximation algorithmmaximum independent setunit disk graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Approximation algorithms for maximum independent set of a unit disk graph
• Faster approximation for maximum independent set on unit disk graph
• Efficient independent set approximation in unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1507300

Cites work

• Approximation algorithms for maximum independent set of a unit disk graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Label placement by maximum independent set in rectangles
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Simple heuristics for unit disk graphs

Cited in

(5)

• Efficient independent set approximation in unit disk graphs
• Dynamic programming optimization in line of sight networks
• Faster approximation for maximum independent set on unit disk graph
• Approximation algorithms for maximum independent set of a unit disk graph
• Approximation algorithms for maximum independent set of pseudo-disks

This page was built for publication: Improved algorithm for maximum independent set on unit disk graph

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