最短路問題と最長路問題

概要

論文の詳細を見る
Many of combinatorial optimization problems can be formulated as the linear programming (LP) problem. So they can be solved not only by their proper combinatorial algorithms but also by the algorithm in the LP problem. In the present paper, we focus on the shortest path problem and the longest path problem which are typical examples of the combinatorial optimization problem on the flow-networks. The shortest path problem is the problem for finding the path whose weight is minimal. Conversely, the longest path problem is the problem for finding the path whose weight is maximal. The purpose of our study is to formulate the shortest path problem and the longest path problem as the LP problem, and to find an algorithm for solving the longest path problem. In the present paper, we give the formulation of the shortest path problem as the LP problem. However, the longest path problem is not easy to formulate as the LP problem. So we give one formulation of the longest path problem by using rank condition, and give a combinatorial algorithm for the longest path problem.
2013-07-00