Browse

추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군
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.accessioned2009-07-10T07:24:22Z-
dc.date.available2009-07-10T07:24:22Z-
dc.date.issued2001-
dc.identifier.citationJournal of the Korean Institute of Industrial Engineers, 27(4), 379-383en
dc.identifier.issn1225-0988-
dc.identifier.urihttps://hdl.handle.net/10371/5343-
dc.description.abstractThe 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.isoko-
dc.publisher대한산업공학회 = Korean Institute of Industrial Engineersen
dc.subjectrestricted shortest path problemen
dc.subjectfully polynomial approximation schemeen
dc.title추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군en
dc.title.alternativeA Simple Fully Polynomial Approximation Scheme for the Restricted Shortest Path Problemen
dc.typeArticleen
dc.contributor.AlternativeAuthorHong, Sung-Pil-
dc.contributor.AlternativeAuthorChung, Sung-Jin-
dc.contributor.AlternativeAuthorPark, Bum Hwan-
dc.citation.journaltitle대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
Files in This Item:
  • mendeley

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

Browse