Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

DOI10.1007/S10898-022-01163-XMaRDI QIDQ2089871zbMATH OpenOpenAlexFDO

Authors Jianping Li, Wencheng Wang, Junran Lichen, Suding Liu, Pengxiang Pan

Publication date 24 October 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-022-01163-x

zbMATH Keywords

approximation algorithmscombinatorial optimizationexact algorithmsline-capacitated Steiner treeslocations of lines

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• 1-line minimum rectilinear Steiner trees and related problems
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Automata, Languages and Programming
• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)

Cites work

• Approximation algorithms for a capacitated network design problem
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• scientific article; zbMATH DE number 3912403 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• Maximum matching and a polyhedron with 0,1-vertices
• On Steiner Minimal Trees with Rectilinear Distance
• On the Complexity of Numerical Analysis
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Spanning Trees and Optimization Problems
• Steiner tree problems
• Steiner tree problems in computer communication networks.
• Survivable network design: the capacitated minimum spanning network problem
• The Complexity of Computing Steiner Minimal Trees
• The complexity of the capacitated tree problem
• Transitions in geometric minimum spanning trees
• Variations on the Euclidean Steiner tree problem and algorithms

Cited in

(5)

• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• 1-line minimum rectilinear Steiner trees and related problems
• On the edge capacitated Steiner tree problem
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Automata, Languages and Programming

This page was built for publication: Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

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