Improved algorithms for path partition and related problems

DOI10.1016/j.orl.2011.08.001zbMath1235.90170MaRDI QIDQ408433

Danny Z. Chen, Haitao Wang

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.08.001

zbMATH Keywords

algorithms; path partition; Monge property; \(k\)-link shortest path; web proxies placement

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Related Items

New algorithms for facility location problems on the real line

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum \(L_k\) path partitioning-an illustration of the Monge property
• Geometric applications of a matrix-searching algorithm
• Improved complexity bounds for location problems on the real line
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• Clustering on trees
• Path equipartition in the Chebyshev norm
• Monge strikes again: Optimal placement of web proxies in the internet
• Most uniform path partitioning and its use in image processing
• The shifting algorithm technique for the partitioning of trees
• A Shifting Algorithm for Min-Max Tree Partitioning
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
• New Algorithms for 1-D Facility Location and Path Equipartition Problems