The partial sum criterion for Steiner trees in graphs and shortest paths

DOI10.1016/S0377-2217(96)00113-0MaRDI QIDQ1278596zbMATH OpenOpenAlexFDO

Authors A. Volgenant, Cees Duin

Publication date 22 February 1999

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(96)00113-0

zbMATH Keywords

bottleneck shortest pathbottleneck spanning treeminmax Steiner tree problempartial sum criterion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions
• scientific article; zbMATH DE number 222076
• The bottleneck selected‐internal and partial terminal Steiner tree problems
• A faster approximation algorithm for the Steiner problem in graphs

Cites work

• K-Sum Linear Programming
• A linear time algorithm for the maximum capacity path problem
• An augmenting path method for solving linear bottleneck assignment problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding k edge-disjoint spanning trees of minimum total weight in a network: An application of matroid theory
• scientific article; zbMATH DE number 3773364 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• k-Eccentricity and absolute k-centrum of a probabilistic tree
• k-sum optimization problems
• On \(k\)-sum optimization
• On minimizing the sum of k tardinesses
• Reduction tests for the steiner problem in grapsh
• Shortest Path and Network Flow Algorithms
• Some generalizations of the steiner problem in graphs
• The Min-Max Spanning Tree Problem and some extensions
• The Steiner tree problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(8)

• The bottleneck \(k\)-MST
• Improved polynomial algorithms for robust bottleneck problems with interval data
• Solving some lexicographic multi-objective combinatorial problems
• A bi-objective network design approach for discovering functional modules linking Golgi apparatus fragmentation and neuronal death
• Bridging \(k\)-sum and CVaR optimization in MILP
• Bottleneck Steiner tree with bounded number of Steiner vertices
• The Euclidean bottleneck full Steiner tree problem
• Fast algorithm for multicast and data gathering in wireless networks

This page was built for publication: The partial sum criterion for Steiner trees in graphs and shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1278596)