Publications
Detailed Information
추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군 : A Simple Fully Polynomial Approximation Scheme for the Restricted Shortest Path Problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 홍성필 | - |
dc.contributor.author | 정성진 | - |
dc.contributor.author | 박범환 | - |
dc.date.accessioned | 2009-07-10T07:24:22Z | - |
dc.date.available | 2009-07-10T07:24:22Z | - |
dc.date.issued | 2001 | - |
dc.identifier.citation | Journal of the Korean Institute of Industrial Engineers, 27(4), 379-383 | en |
dc.identifier.issn | 1225-0988 | - |
dc.identifier.uri | https://hdl.handle.net/10371/5343 | - |
dc.description.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. | en |
dc.description.sponsorship | 이 연구는 1999년도 한국학술진흥재단의 연구비에 의하여 지원되었음(KRF-99-041-E00125) | en |
dc.language.iso | ko | - |
dc.publisher | 대한산업공학회 = Korean Institute of Industrial Engineers | en |
dc.subject | restricted shortest path problem | en |
dc.subject | fully polynomial approximation scheme | en |
dc.title | 추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군 | en |
dc.title.alternative | A Simple Fully Polynomial Approximation Scheme for the Restricted Shortest Path Problem | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | Hong, Sung-Pil | - |
dc.contributor.AlternativeAuthor | Chung, Sung-Jin | - |
dc.contributor.AlternativeAuthor | Park, Bum Hwan | - |
dc.citation.journaltitle | 대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.