On the minimum corridor connection problem and other generalized geometric problems
From MaRDI portal
Publication:833722
DOI10.1016/j.comgeo.2009.05.001zbMath1200.05215WikidataQ57338956 ScholiaQ57338956MaRDI QIDQ833722
Corinne Feremans, Hans L. Bodlaender, Alexander Grigoriev, Thomas Wolle, Eelko Penninkx, 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
complexity; approximations; exact algorithms; generalized geometric problems; minimum corridor connection
52B55: Computational aspects related to convexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- 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.
- 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