Subexponential-time parameterized algorithm for Steiner tree on planar graphs

DOI10.4230/LIPICS.STACS.2013.353MaRDI QIDQ2957897zbMATH OpenOpenAlexFDO

Authors Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen

Publication date 30 January 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2013.353

zbMATH Keywords

planar graphSteiner treesubexponential-time algorithms

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Subexponential parameterized algorithms
• Subexponential Parameterized Algorithms
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Fast sub-exponential algorithms and compactness in planar graphs

Cited in

(21)

• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• Linear kernels for outbranching problems in sparse digraphs
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Fast sub-exponential algorithms and compactness in planar graphs
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Survivable network design for group connectivity in low-treewidth graphs
• Parameterized approximation algorithms for bidirected Steiner network problems
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Parameterized complexity of directed Steiner tree on sparse graphs
• Subexponential Parameterized Algorithms
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• On the complexity of the cable-trench problem
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• An O(n n) approximation scheme for Steiner tree in planar graphs
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands

This page was built for publication: Subexponential-time parameterized algorithm for Steiner tree on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957897)