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/

zbMATH Keywords

parameterized algorithmsrectilinear graphsSteiner arborescence

Mathematics Subject Classification ID

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)

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

Cited in

(10)

• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• Quasipolynomial representation of transversal matroids with applications in parameterized complexity
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Finding even subgraphs even faster
• Path-contractions, edge deletions and connectivity preservation
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs

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)