Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems

DOI10.1007/978-3-642-02927-1_59zbMath1248.68258OpenAlexW1593947471MaRDI QIDQ3638075

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_59

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (28)

Spotting Trees with Few Leaves ⋮ Set multi-covering via inclusion-exclusion ⋮ Spotting Trees with Few Leaves ⋮ Computing optimal Steiner trees in polynomial space ⋮ Improved parameterized algorithms for network query problems ⋮ Exponential approximation schemata for some network design problems ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ On the parameterized complexity of dynamic problems ⋮ Faster algorithm for optimum Steiner trees ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ An exact algorithm for connected red-blue dominating set ⋮ Parameterized complexity of team formation in social networks ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ FPT algorithms for connected feedback vertex set ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ The maximum binary tree problem ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Parameterized Complexity of Team Formation in Social Networks ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Unnamed Item ⋮ Constrained multilinear detection and generalized graph motifs

This page was built for publication: Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems