File Download
There are no files associated with this item.
Supplementary

Citations:
 Appears in Collections:
Conference Paper: Algorithms for Finding Optimal Disjoint Paths Around a Rectangle
Title  Algorithms for Finding Optimal Disjoint Paths Around a Rectangle 

Authors  
Issue Date  1997 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Proceedings of the 8th International Symposium on Algorithms and Computation (ISAAC '97), Singapore, 1719 December 1997. In Lecture Notes in Computer Science, 1997, v. 1350, p. 314323 How to Cite? 
Abstract  We give algorithms to find the optimal disjoint paths around a rectangle. The set of disjoint paths connects a set of sources to a set of sinks (no fixed pairing between the sources and sinks) on the boundary of a rectangle where either the longest path length or the total path length is minimized. One algorithm finds the set of disjoint paths with the longest path length minimized in O(n log n) time and the other finds the set of disjoint paths with the total path length minimized in O(n 2) time. In particular, if the sets of sources and sinks lie on a straight line, the set of disjoint paths with the minimum longest path length or minimum total path length can be found in O(n) or O(n 2) time respectively. 
Persistent Identifier  http://hdl.handle.net/10722/93143 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Chan, WT   
dc.contributor.author  Chin, FYL   
dc.date.accessioned  20100925T14:52:11Z   
dc.date.available  20100925T14:52:11Z   
dc.date.issued  1997   
dc.identifier.citation  Proceedings of the 8th International Symposium on Algorithms and Computation (ISAAC '97), Singapore, 1719 December 1997. In Lecture Notes in Computer Science, 1997, v. 1350, p. 314323   
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/93143   
dc.description.abstract  We give algorithms to find the optimal disjoint paths around a rectangle. The set of disjoint paths connects a set of sources to a set of sinks (no fixed pairing between the sources and sinks) on the boundary of a rectangle where either the longest path length or the total path length is minimized. One algorithm finds the set of disjoint paths with the longest path length minimized in O(n log n) time and the other finds the set of disjoint paths with the total path length minimized in O(n 2) time. In particular, if the sets of sources and sinks lie on a straight line, the set of disjoint paths with the minimum longest path length or minimum total path length can be found in O(n) or O(n 2) time respectively.   
dc.language  eng   
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science   
dc.title  Algorithms for Finding Optimal Disjoint Paths Around a Rectangle   
dc.type  Conference_Paper   
dc.identifier.email  Chin, FYL: chin@cs.hku.hk   
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.identifier.doi  10.1007/3540638903_34   
dc.identifier.hkuros  31088   
dc.identifier.volume  1350   
dc.identifier.spage  314   
dc.identifier.epage  323   
dc.publisher.place  Germany   