Minimum \(L_k\) path partitioning-an illustration of the Monge property

DOI10.1016/j.orl.2007.03.010zbMath1161.90517OpenAlexW2032363728MaRDI QIDQ924884

Pei-Hao Ho, Arie Tamir, Bang Ye Wu

Publication date: 29 May 2008

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

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

zbMATH Keywords

partitiondynamic programmingconvexityMonge property

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Improved algorithms for path partition and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for concave one-dimensional dynamic programming
• Improved complexity bounds for location problems on the real line
• Dynamic programming with convexity, concavity and sparsity
• Path equipartition in the Chebyshev norm
• Most uniform path partitioning and its use in image processing
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Sequence comparison with mixed convex and concave costs
• The concave least-weight subsequence problem revisited
• Efficient partitioning of sequences
• Fair dissections of spiders, worms, and caterpillars
• Optimal Partitioning of Sequences

This page was built for publication: Minimum \(L_k\) path partitioning-an illustration of the Monge property