On the minimum corridor connection problem and other generalized geometric problems

DOI10.1016/J.COMGEO.2009.05.001MaRDI QIDQ833722zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Thomas Wolle, René 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

complexityexact algorithmsapproximationsgeneralized geometric problemsminimum corridor connection

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1163704 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 219265 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A PTAS for TSP with neighborhoods among fat regions in the plane
• A Separator Theorem for Planar Graphs
• A better heuristic for orthogonal graph drawings
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms – ESA 2005
• An improved approximation scheme for the Group Steiner Problem
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Automata, Languages and Programming
• Automata, Languages and Programming
• Call routing and the ratcatcher
• Complexity of the minimum-length corridor problem
• Dynamic Programming and Fast Matrix Multiplication
• Generalized network design problems.
• New upper bounds on the decomposability of planar graphs
• On generalized minimum spanning trees
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• On the complexity of approximating TSP with neighborhoods and related problems
• Planar branch decompositions. I: The ratcatcher
• Planar branch decompositions. II: The cycle method
• Rectilinear group Steiner trees and applications in VLSI design
• TSP with neighborhoods of varying size
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(7)

• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• Connecting face hitting sets in planar graphs
• THE MINIMUM GUARDING TREE PROBLEM
• Complexity of minimum corridor guarding problems
• Constant-factor approximation for TSP with disks
• Minimum length corridor problem on grids

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)