Subexponential algorithms for rectilinear Steiner tree and arborescence problems
DOI10.4230/LIPICS.SOCG.2016.39zbMATH Open1387.68180OpenAlexW2472796018MaRDI QIDQ3132873FDOQ3132873
Authors: Fedor V. Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 
Publication date: 30 January 2018
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5931/pdf/LIPIcs-SoCG-2016-39.pdf/
Recommendations
- Subexponential algorithms for rectilinear Steiner tree and arborescence problems
- Solving rectilinear Steiner tree problems exactly in theory and practice
- On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
- The rectilinear Steiner arborescence problem
- Improved Computation of Optimal Rectilinear Steiner Minimal Trees
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cited In (10)
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- Subexponential algorithms for rectilinear Steiner tree and arborescence problems
- Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Title not available (Why is that?)
- Quasipolynomial representation of transversal matroids with applications in parameterized complexity
- Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
- Path-contractions, edge deletions and connectivity preservation
- Finding even subgraphs even faster
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
This page was built for publication: Subexponential algorithms for rectilinear Steiner tree and arborescence problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132873)
