최단경로문제에서 k개의 치명호를 찾는 방법 = A Method for Finding the k Most Vital Arcs in the Shortest Path Problem

다국어 초록 (Multilingual Abstract)

This paper deals with a mathematical model and an algorithm for the problem of determining k most vital arcs in the shortest path problem.
First, we propose a 0-1 integer programming model for finding k most vital arcs in shortest path problem given the ordered set of paths with cardinality q. Next, we also propose an algorithm for finding k most vital arcs in the shortest path problem which uses the 0-1 integer programming model and shortest path algorithm and maximum flow algorithms repeatedly.
Malik et al. proposed a non-polynomial algorithm to solve the problem, but their algorithm was contradicted by Bar-Noy et al. with a counter example to the algorithm in 1995. But using our algorithm. the exact solution can be found differently from the algorithm of Malik et al.