Computing optimal Steiner trees in polynomial space
From MaRDI portal
Publication:2392926
DOI10.1007/S00453-012-9612-ZzbMATH Open1269.05049DBLPjournals/algorithmica/FominGKLS13OpenAlexW2155235203WikidataQ60488414 ScholiaQ60488414MaRDI QIDQ2392926FDOQ2392926
Authors: Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, Daniel Lokshtanov, Saket Saurabh 
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
Recommendations
- Faster Steiner Tree Computation in Polynomial-Space
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22)
Cites Work
- Title not available (Why is that?)
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- A measure \& conquer approach for the analysis of exact algorithms
- The Traveling Salesman Problem for Cubic Graphs
- A partial k-arboretum of graphs with bounded treewidth
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Title not available (Why is that?)
- Automata, Languages and Programming
- The Steiner tree problem
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Combinatorial bounds via measure and conquer
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- An improved LP-based approximation for Steiner tree
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Fourier meets M\"{o}bius: fast subset convolution
- Title not available (Why is that?)
- Solving connected dominating set faster than \(2^n\)
- The steiner problem in graphs
- The Steiner problem with edge lengths 1 and 2
- Dynamic programming for minimum Steiner trees
- Faster Steiner Tree Computation in Polynomial-Space
- Measure and conquer
- Expected Computation Time for Hamiltonian Path problem
- A Faster Algorithm for the Steiner Tree Problem
- A note on the complexity of minimum dominating set
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Dynamic programming meets the principle of inclusion and exclusion
- Algorithms and Data Structures
- Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- A probably fast, provably optimal algorithm for rectilinear Steiner trees
- Inclusion and exclusion algorithm for the Hamiltonian path problem
- Title not available (Why is that?)
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
- Title not available (Why is that?)
Cited In (13)
- Inexact graph matching using a hierarchy of matching processes
- Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Dynamic programming for minimum Steiner trees
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Faster Steiner Tree Computation in Polynomial-Space
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Improved Steiner tree algorithms for bounded treewidth
This page was built for publication: Computing optimal Steiner trees in polynomial space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392926)
