The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
An Algorithm for Shortest Paths in Bipartitie Digraphs with Concave Weight Matrices and its Applications
Xin He, Zhi-Zhong Chen,
Pages. 65-80
Abstract
Contents 1. Introduction 2. The TSP for points on a convex polygon 3. The MLP for points on
a straight line 4. Solving the SPBD problem 4.1. The LWS problem
and the enhanced LWS problem 4.2. Reduction 4.3. An algorithm for
the enhanced LWS problem 4.4. The SPBD algorithm and its
complexity 5. Conclusion
Key words graph algorithm, shortest path, traveling salesman problem, minimum latency tour problem, concave matrix
Mathmatical Subject Classification 68Q25, 68R10