SHERP

추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군
A Simple Fully Polynomial Approximation Scheme for the Restricted Shortest Path Problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
홍성필; 정성진; 박범환
Issue Date
2001
Publisher
대한산업공학회 = Korean Institute of Industrial Engineers
Citation
Journal of the Korean Institute of Industrial Engineers, 27(4), 379-383
Keywords
restricted shortest path problem; fully polynomial approximation scheme
Abstract
The restricted shortest path problem is known to be weakly NP-hard and solvable in pseudo-polynomial time. Four fully polynomial approximation schemes (FPAS) are available in the literature, and most of these are based on pseudo-polynomial algorithms. In this paper, we propose a new FPAS that can be easily derived from a combination of a set of standard techniques. Although the complexity of the suggested algorithm is not as good as the fastest one available in the literature, it is practical in the sense that it does not rely on the bound tightening phase based on approximate binary search as in Hassin's fastest algorithm. In addition, we provide a review of standard techniques of existing works as a useful reference.
ISSN
1225-0988
Language
Korean
URI
http://hdl.handle.net/10371/5343
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse