Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
From MaRDI portal
Publication:3638075
DOI10.1007/978-3-642-02927-1_59zbMath1248.68258MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Spotting Trees with Few Leaves, Unnamed Item, Implications, conflicts, and reductions for Steiner trees, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, Solving Steiner trees: Recent advances, challenges, and perspectives, Constrained multilinear detection and generalized graph motifs, Exponential approximation schemata for some network design problems, The kernelization complexity of connected domination in graphs with (no) small cycles, Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs, Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, An exact algorithm for connected red-blue dominating set, FPT algorithms for connected feedback vertex set, Set multi-covering via inclusion-exclusion, On the parameterized complexity of dynamic problems, Parameterized complexity of team formation in social networks, Faster algorithm for optimum Steiner trees, Capacitated domination faster than \(O(2^n)\), The maximum binary tree problem, Algorithmic aspects of Steiner convexity and enumeration of Steiner trees, Computing optimal Steiner trees in polynomial space, Improved parameterized algorithms for network query problems, Sharp separation and applications to exact and parameterized algorithms, Parameterized Complexity of Team Formation in Social Networks, Invitation to Algorithmic Uses of Inclusion–Exclusion, Enumerate and Measure: Improving Parameter Budget Management, Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting, Planar k-Path in Subexponential Time and Polynomial Space, Spotting Trees with Few Leaves
