Faster Steiner Tree Computation in Polynomial-Space

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

Mathematics Subject Classification ID

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