Shifting strategy for geometric graphs without geometry

DOI10.1007/s10878-010-9319-5zbMath1269.90131MaRDI QIDQ454249

Imran A. Pirwani

Publication date: 1 October 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9319-5

zbMATH Keywords

computational geometry; approximation algorithms; shifting strategy

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Some results on greedy embeddings in metric spaces
• Unit disk graph recognition is NP-hard
• Polynomial time approximation schemes for base station coverage with minimum total radii
• On a conjecture related to geometric routing
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On Metric Clustering to Minimize the Sum of Radii
• Good Quality Virtual Realization of Unit Ball Graphs
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Bypassing the embedding
• Succinct Greedy Geometric Routing in the Euclidean Plane
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation schemes for wireless networks
• On the locality of bounded growth
• Algorithmic Aspects of Wireless Sensor Networks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Distributed Computing
• Algorithms – ESA 2005
• Algorithms – ESA 2005
• Graph-Theoretic Concepts in Computer Science
• Approximation and Online Algorithms
• The intrinsic dimensionality of graphs
• A tight bound on approximating arbitrary metrics by tree metrics