A faster approximation algorithm for the Steiner problem in graphs

DOI10.1007/BF00289500zbMath0592.68062OpenAlexW1993553699MaRDI QIDQ5903117

No author found.

Publication date: 1986

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289500

zbMATH Keywords

distance graphSteiner treegeneralized minimum spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree, Fast heuristic algorithms for rectilinear Steiner trees, A super-stabilizing \(\log(n)\)-approximation algorithm for dynamic Steiner trees, Branch-and-bound as a higher-order function, The multi-weighted Steiner tree problem, Path-distance heuristic for the Steiner problem in undirected networks, Heuristics for the Steiner problem in graphs, THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM, Steiner's problem in graphs: Heuristic methods, A faster approximation algorithm for the Steiner problem in graphs, The algorithmic structure of a decision support system for a design of a district heating network, Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE, The Steiner problem in distributed computing systems

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A fast algorithm for Steiner trees
• Some remarks on the Steiner problem
• A short proof of a result of Pollak on Steiner minimal trees
• An integer linear programming approach to the steiner problem in graphs
• Steiner Minimal Trees
• An algorithm for the steiner problem in graphs