On the minimum corridor connection problem and other generalized geometric problems

DOI10.1016/j.comgeo.2009.05.001zbMath1200.05215OpenAlexW2107739573WikidataQ57338956 ScholiaQ57338956MaRDI QIDQ833722

Eelko Penninkx, Hans L. Bodlaender, Alexander Grigoriev, Corinne Feremans, Thomas Wolle, R. A. Sitters

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

zbMATH Keywords

complexityapproximationsexact algorithmsgeneralized geometric problemsminimum corridor connection

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Improved bounds on the planar branchwidth with respect to the largest grid minor size ⋮ Connecting face hitting sets in planar graphs ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Complexity of minimum corridor guarding problems ⋮ THE MINIMUM GUARDING TREE PROBLEM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of the minimum-length corridor problem
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Approximation algorithms for the Geometric Covering Salesman Problem
• A better heuristic for orthogonal graph drawings
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Rectilinear group Steiner trees and applications in VLSI design
• Generalized network design problems.
• An improved approximation scheme for the Group Steiner Problem
• Planar Branch Decompositions I: The Ratcatcher
• Planar Branch Decompositions II: The Cycle Method
• New upper bounds on the decomposability of planar graphs
• A Separator Theorem for Planar Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Approximation algorithms for TSP with neighborhoods in the plane
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms – ESA 2005
• TSP with neighborhoods of varying size
• Automata, Languages and Programming
• Automata, Languages and Programming
• Algorithms - ESA 2003
• On generalized minimum spanning trees