Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38308
DC FieldValueLanguage
dc.contributor.authorM.J.Atallahen_US
dc.contributor.authorD.Z.Chenen_US
dc.contributor.authorD.T.Leeen_US
dc.date1995-11en_US
dc.date.accessioned2014-06-06T08:00:42Z-
dc.date.available2014-06-06T08:00:42Z-
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/11455/38308-
dc.description.abstractWe give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.en_US
dc.language.isoen_USen_US
dc.publisherSpringer-Verlagen_US
dc.relationAlgorithmica, Volume�14, Issue�5, Page(s) �429-441.en_US
dc.subjectShortest pathsen_US
dc.subjectInterval graphsen_US
dc.subjectCircular-arc graphsen_US
dc.subjectUnion-find algorithmsen_US
dc.subjectMinimum circle coveren_US
dc.titleAn Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-arc Graphs with Applicationsen_US
dc.typeJournal Articlezh_TW
dc.identifier.doi10.1007/BF01192049en_US
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairetypeJournal Article-
item.cerifentitytypePublications-
item.fulltextno fulltext-
item.languageiso639-1en_US-
item.grantfulltextnone-
Appears in Collections:資訊科學與工程學系所
Show simple item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.