The Steiner problem with edge lengths 1 and 2
From MaRDI portal
Publication:1123630
DOI10.1016/0020-0190(89)90039-2zbMath0677.68074OpenAlexW2070664846WikidataQ56490243 ScholiaQ56490243MaRDI QIDQ1123630
Marshall W. Bern, Paul E. Plassmann
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90039-2
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Methods for reconstructing the history of tandem repeats and their application to the human genome., The hardness of approximation: Gap location, Models of greedy algorithms for graph problems, Minimum Certificate Dispersal with Tree Structures, RNC-approximation algorithms for the steiner problem, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, Reoptimization of Steiner trees: changing the terminal set, On the Steiner ratio in 3-space, On component-size bounded Steiner trees, A survey on combinatorial optimization in dynamic environments, 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2, Approximation schemes for node-weighted geometric Steiner tree problems, Computing optimal Steiner trees in polynomial space, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, Steiner trees for hereditary graph classes: a treewidth perspective, Extending the kernel for planar Steiner tree to the number of Steiner vertices, A hard dial-a-ride problem that is easy on average, Approximation algorithms for tree alignment with a given phylogeny, Robust reoptimization of Steiner trees, On the approximability of the maximum common subgraph problem, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, On the low-dimensional Steiner minimum tree problem in Hamming metric, Exponential approximation schemata for some network design problems, Improved Steiner tree algorithms for bounded treewidth, An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2, On the complexity of the bilevel minimum spanning tree problem, Approximation algorithms for Steiner forest: An experimental study, A linear programming based approach to the Steiner tree problem with a fixed number of terminals, Solving Steiner trees: Recent advances, challenges, and perspectives, The Clustered Selected-Internal Steiner Tree Problem, On the approximability of the Steiner tree problem., Steiner tree reoptimization in graphs with sharpened triangle inequality, An ETH-tight algorithm for bidirected Steiner connectivity, Approximating Alternative Solutions, Reoptimization of Steiner Trees, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, Faster algorithm for optimum Steiner trees, Euclidean prize-collecting Steiner forest, Improved non-approximability results for vertex cover with density constraints, GMPLS label space minimization through hypergraph layouts, Connected facility location via random facility sampling and core detouring, Wildlife corridors as a connected subgraph problem, Improved non-approximability results for minimum vertex cover with density constraints, Watchman routes for lines and line segments, On the edge capacitated Steiner tree problem, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Faster Steiner Tree Computation in Polynomial-Space, Differential approximation results for the Steiner tree problem, Strong Steiner Tree Approximations in Practice, An Efficient Approximation Algorithm for the Steiner Tree Problem, Regular Language Constrained Sequence Alignment Revisited, Algorithms for the minimum diameter terminal Steiner tree problem, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, The Bursty Steiner Tree Problem, Approximate solution of NP optimization problems, An improved algorithm for the Steiner tree problem with bounded edge-length, Algorithms for terminal Steiner trees, Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem, Knowing All Optimal Solutions Does Not Help for TSP Reoptimization, A series of approximation algorithms for the acyclic directed Steiner tree problem, The Steiner tree problem on graphs: inapproximability results, The full Steiner tree problem, A near linear time approximation scheme for Steiner tree among obstacles in the plane, On the Hardness of Reoptimization, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\), Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem, Packing trees in communication networks, Travelling on graphs with small highway dimension, Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Class Steiner trees and VLSI-design, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, On approximation algorithms for the terminal Steiner tree problem, Multi-level Steiner Trees, Designing Hypergraph Layouts to GMPLS Routing Strategies, Parameterized analysis of the online priority and node-weighted Steiner tree problems, \(1\)-line minimum rectilinear Steiner trees and related problems, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, Steiner trees in uniformly quasi-bipartite graphs., On the terminal Steiner tree problem., Improved methods for approximating node weighted Steiner trees and connected dominating sets., Unnamed Item, A greedy approximation algorithm for the group Steiner problem, On Hop-Constrained Steiner Trees in Tree-Like Metrics, Moderately exponential time and fixed parameter approximation algorithms, On full Steiner trees in unit disk graphs, The maximum \(f\)-depth spanning tree problem, Approximability of minimum certificate dispersal with tree structures, Multi-Level Steiner Trees.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Worst-case performance of Rayward-Smith's Steiner tree heuristic
- Steiner problem in networks: A survey
- On Steiner Minimal Trees with Rectilinear Distance
- The computation of nearly minimal Steiner trees in graphs
- Steiner Minimal Trees
- A faster approximation algorithm for the Steiner problem in graphs
