On the minimum corridor connection problem and other generalized geometric problems
DOI10.1016/J.COMGEO.2009.05.001zbMATH Open1200.05215OpenAlexW2107739573WikidataQ57338956 ScholiaQ57338956MaRDI QIDQ833722FDOQ833722
René A. Sitters, Eelko Penninkx, Hans L. Bodlaender, Alexander Grigoriev, Corinne Feremans, Thomas Wolle
Publication date: 14 August 2009
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.05.001
Recommendations
- On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
- Complexity of the minimum-length corridor problem
- A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane
- Approximating corridors and tours via restriction and relaxation techniques
- Complexity of minimum corridor guarding problems
Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)
Cites Work
- Title not available (Why is that?)
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Approximation algorithms for TSP with neighborhoods in the plane
- A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
- Title not available (Why is that?)
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- Dynamic Programming and Fast Matrix Multiplication
- A better heuristic for orthogonal graph drawings
- Title not available (Why is that?)
- Generalized network design problems.
- On generalized minimum spanning trees
- Planar branch decompositions. I: The ratcatcher
- Planar branch decompositions. II: The cycle method
- New upper bounds on the decomposability of planar graphs
- Approximation algorithms for the Geometric Covering Salesman Problem
- Approximation schemes for NP-hard geometric optimization problems: a survey
- An improved approximation scheme for the Group Steiner Problem
- TSP with neighborhoods of varying size
- Automata, Languages and Programming
- Title not available (Why is that?)
- Algorithms – ESA 2005
- Automata, Languages and Programming
- Complexity of the minimum-length corridor problem
- Algorithms - ESA 2003
- Rectilinear group Steiner trees and applications in VLSI design
- On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
Cited In (6)
- Constant-Factor Approximation for TSP with Disks
- Connecting face hitting sets in planar graphs
- THE MINIMUM GUARDING TREE PROBLEM
- Complexity of minimum corridor guarding problems
- On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
This page was built for publication: On the minimum corridor connection problem and other generalized geometric problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q833722)
