An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays

DOI10.1016/S0020-0190(98)00137-9zbMath1339.68115OpenAlexW2120168175MaRDI QIDQ293394

Pedro Jodrá, F. Javier Tejel, Alfredo Daniel Garcia

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00137-9

zbMATH Keywords

computational complexitytraveling salesman problemcomputational geometryMonge matrices: dynamic programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)

Related Items (2)

A note on the traveling repairman problem ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon

Cites Work

• Geometric applications of a matrix-searching algorithm
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• The convex-hull-and-line traveling salesman problem: A solvable case
• Perspectives of Monge properties in optimization
• Efficient special case algorithms for the n-line planar traveling salesman problem
• Improved Algorithms for Economic Lot Size Problems
• On-line dynamic programming with applications to the prediction of RNA secondary structure

This page was built for publication: An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays