Faster Steiner Tree Computation in Polynomial-Space
From MaRDI portal
Publication:3541105
DOI10.1007/978-3-540-87744-8_36zbMath1158.68429OpenAlexW2129628945MaRDI QIDQ3541105
Fabrizio Grandoni, Dieter Kratsch, Fedor V. Fomin
Publication date: 25 November 2008
Published in: Algorithms - ESA 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_36
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (10)
Computing optimal Steiner trees in polynomial space ⋮ Probability Steiner trees and maximum parsimony in phylogenetic analysis ⋮ Exponential approximation schemata for some network design problems ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Faster algorithm for optimum Steiner trees ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
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
- 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
- Dynamic programming for minimum Steiner trees
- Parametrized complexity theory.
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Fourier meets M\"{o}bius: fast subset convolution
- Measure and conquer
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- 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
- 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
This page was built for publication: Faster Steiner Tree Computation in Polynomial-Space