Computing optimal Steiner trees in polynomial space
From MaRDI portal
Publication:2392926
DOI10.1007/s00453-012-9612-zzbMath1269.05049OpenAlexW2155235203WikidataQ60488414 ScholiaQ60488414MaRDI QIDQ2392926
Saket Saurabh, Fabrizio Grandoni, Fedor V. Fomin, Dieter Kratsch, Daniel Lokshtanov
Publication date: 5 August 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9612-z
Trees (05C05) Extremal problems in graph theory (05C35) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ Inexact graph matching using a hierarchy of matching processes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inclusion and exclusion algorithm for the Hamiltonian path problem
- Solving connected dominating set faster than \(2^n\)
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- The Steiner problem with edge lengths 1 and 2
- Dynamic programming meets the principle of inclusion and exclusion
- The Steiner tree problem
- A partial k-arboretum of graphs with bounded treewidth
- Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
- A note on the complexity of minimum dominating set
- Dynamic programming for minimum Steiner trees
- An improved LP-based approximation for steiner tree
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A measure & conquer approach for the analysis of exact algorithms
- Faster Steiner Tree Computation in Polynomial-Space
- Fourier meets M\"{o}bius: fast subset convolution
- Measure and conquer
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Expected Computation Time for Hamiltonian Path problem
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- A probably fast, provably optimal algorithm for rectilinear Steiner trees
- Combinatorial bounds via measure and conquer
- The Traveling Salesman Problem for Cubic Graphs
- Parameterized and Exact Computation
- Algorithms and Data Structures
- A Faster Algorithm for the Steiner Tree Problem
- The steiner problem in graphs
- Automata, Languages and Programming
