The algebraic Monge property and path problems

DOI10.1016/j.dam.2004.06.001zbMath1087.90060OpenAlexW2061072106MaRDI QIDQ1765525

Peter Brucker, Lawrence L. Larmore, James K. Park, Wolfgang W. Bein

Publication date: 23 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.001

zbMATH Keywords

combinatorial problemsbottleneck shortest path problems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (2)

Technical note: Split algorithm in \(O(n)\) for the capacitated vehicle routing problem ⋮ On the generality of the greedy algorithm for solving matroid base problems

Cites Work

• Unnamed Item
• Unnamed Item
• Linear verification for spanning trees
• Geometric applications of a matrix-searching algorithm
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• On the recognition of permuted bottleneck Monge matrices
• Perspectives of Monge properties in optimization
• The Least Weight Subsequence Problem
• The concave least-weight subsequence problem revisited
• Algorithms for two bottleneck optimization problems
• On-line dynamic programming with applications to the prediction of RNA secondary structure

This page was built for publication: The algebraic Monge property and path problems