Computing optimal Steiner trees in polynomial space
From MaRDI portal
Publication:2392926
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
Cites work
- scientific article; zbMATH DE number 4191148 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 750011 (Why is no real title available?)
- scientific article; zbMATH DE number 1445376 (Why is no real title available?)
- scientific article; zbMATH DE number 970831 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Faster Algorithm for the Steiner Tree Problem
- A measure \& conquer approach for the analysis of exact algorithms
- A note on the complexity of minimum dominating set
- A partial k-arboretum of graphs with bounded treewidth
- A probably fast, provably optimal algorithm for rectilinear Steiner trees
- Algorithms and Data Structures
- An improved LP-based approximation for Steiner tree
- Automata, Languages and Programming
- Combinatorial bounds via measure and conquer
- Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
- Dynamic programming for minimum Steiner trees
- Dynamic programming meets the principle of inclusion and exclusion
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
- Expected Computation Time for Hamiltonian Path problem
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Faster Steiner Tree Computation in Polynomial-Space
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- Fourier meets M\"{o}bius: fast subset convolution
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Inclusion and exclusion algorithm for the Hamiltonian path problem
- Measure and conquer
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Parameterized and Exact Computation
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- Solving connected dominating set faster than \(2^n\)
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
- The Traveling Salesman Problem for Cubic Graphs
- The steiner problem in graphs
Cited in
(13)- Faster Steiner Tree Computation in Polynomial-Space
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Inexact graph matching using a hierarchy of matching processes
- Improved Steiner tree algorithms for bounded treewidth
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Dynamic programming for minimum Steiner trees
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
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)
