Two variations of the minimum Steiner problem

DOI10.1007/s10878-005-5487-0zbMath1066.90105OpenAlexW2077016363MaRDI QIDQ1774532

Da-Wei Wang, Kuo-Hui Tsai, Der-Tsai Lee, Tsan-sheng Hsu

Publication date: 17 May 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-005-5487-0

zbMATH Keywords

directed acyclic graphNP-hardpolynomial timeminimum Steiner networkminimum union paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (2)

Maximizing a submodular function with viability constraints ⋮ On the clustered Steiner tree problem

Cites Work

• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The rectilinear Steiner arborescence problem
• The Steiner tree problem
• Worst-case performance of some heuristics for Steiner's problem in directed graphs
• Directed Steiner problems with connectivity constraints
• A dual ascent approach for steiner tree problems on a directed graph
• Steiner problem in networks: A survey
• An integer linear programming approach to the steiner problem in graphs
• Finding a minimum equivalent graph of a digraph
• Cost-minimal trees in directed acyclic graphs
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• Steiner tree problems

This page was built for publication: Two variations of the minimum Steiner problem