Subexponential algorithms for rectilinear Steiner tree and arborescence problems

DOI10.4230/LIPICS.SOCG.2016.39MaRDI QIDQ3132873zbMATH OpenOpenAlexFDO

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

(11)

• 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
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• 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
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
• 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)