Improved Algorithm for Maximum Independent Set on Unit Disk Graph

DOI10.1007/978-3-319-29221-2_18zbMath1417.68288OpenAlexW2397470036MaRDI QIDQ2795948

Ramesh K. Jallu, Unnamed Author

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

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

Related Items (2)

Faster approximation for maximum independent set on unit disk graph ⋮ Dynamic programming optimization in line of sight networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of a unit disk graph
• Label placement by maximum independent set in rectangles
• Approximation schemes for covering and packing problems in image processing and VLSI
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Improved Algorithm for Maximum Independent Set on Unit Disk Graph