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

DOI10.1016/S0020-0190(98)00137-9MaRDI QIDQ293394zbMATH OpenOpenAlexFDO

Authors Pedro Jodrá, Alfredo García, Javier Tejel

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 complexitycomputational geometrytraveling salesman problemMonge matrices: dynamic programming

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1929930
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Spanning trees and shortest paths in Monge graphs
• An algorithm for the detection and construction of Monge sequences

Cites work

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

Cited in

(3)

• Travelling salesman paths on Demidenko matrices
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• A note on the traveling repairman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293394)