Shifting strategy for geometric graphs without geometry

DOI10.1007/S10878-010-9319-5zbMATH Open1269.90131OpenAlexW1982549992MaRDI QIDQ454249FDOQ454249

Authors: 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

Recommendations

• Shifting strategy for geometric graphs without geometry
• Polynomial-time approximation schemes for geometric graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation Algorithms for Geometric Intersection Graphs

zbMATH Keywords

computational geometryapproximation algorithmsshifting strategy

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

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

Cited In (1)

• Shifting strategy for geometric graphs without geometry

This page was built for publication: Shifting strategy for geometric graphs without geometry

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