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

DOI10.1007/BF02574380zbMath0819.68084OpenAlexW2024353273MaRDI QIDQ1338956

Takeshi Tokuyama, Alok Aggarwal, Baruch Schieber

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 graphtime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Directed graphs (digraphs), tournaments (05C20)

Related Items

Monge matrices make maximization manageable, TOPOLOGICAL PEELING AND APPLICATIONS, Technical note: Split algorithm in \(O(n)\) for the capacitated vehicle routing problem, The directional \(p\)-median problem: definition, complexity, and algorithms, Perspectives of Monge properties in optimization, Consecutive interval query and dynamic programming on intervals, Absent Subsequences in Words, Improved algorithms for path partition and related problems, A circular matrix-merging algorithm with application in volumetric intensity-modulated arc therapy, Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane, New algorithms for facility location problems on the real line, Shape rectangularization problems in intensity-modulated radiation therapy, The algebraic Monge property and path problems, Fitting a step function to a point set, Distribution-aware compressed full-text indexes, EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION, Unnamed Item, POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA, Finding the k Shortest Paths, Bicriteria Data Compression

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