Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications

DOI10.1007/BF02574380zbMath0819.68084MaRDI QIDQ1338956

Takeshi Tokuyama, Baruch Schieber, Alok Aggarwal

Publication date: 27 November 1994

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131331

zbMATH Keywords

directed acyclic graph; time complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

05C20: Directed graphs (digraphs), tournaments

Related Items

EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION, TOPOLOGICAL PEELING AND APPLICATIONS, POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA, Improved algorithms for path partition and related problems, Shape rectangularization problems in intensity-modulated radiation therapy, Fitting a step function to a point set, The directional \(p\)-median problem: definition, complexity, and algorithms, Consecutive interval query and dynamic programming on intervals, The algebraic Monge property and path problems, Monge matrices make maximization manageable, Perspectives of Monge properties in optimization, Finding the k Shortest Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diameter, width, closest line pair, and parametric searching
• Geometric applications of a matrix-searching algorithm
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Searching, Merging, and Sorting in Parallel Computation
• Finding Extremal Polygons
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• The concave least-weight subsequence problem revisited
• Optimal quantization by matrix searching
• Slowing down sorting networks to obtain faster sorting algorithms
• On-line dynamic programming with applications to the prediction of RNA secondary structure