File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Algorithms for Finding Optimal Disjoint Paths Around a Rectangle

TitleAlgorithms for Finding Optimal Disjoint Paths Around a Rectangle
Authors
Issue Date1997
PublisherSpringer 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, 17-19 December 1997. In Lecture Notes in Computer Science, 1997, v. 1350, p. 314-323 How to Cite?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/93143
ISSN
2023 SCImago Journal Rankings: 0.606

 

DC FieldValueLanguage
dc.contributor.authorChan, WT-
dc.contributor.authorChin, FYL-
dc.date.accessioned2010-09-25T14:52:11Z-
dc.date.available2010-09-25T14:52:11Z-
dc.date.issued1997-
dc.identifier.citationProceedings of the 8th International Symposium on Algorithms and Computation (ISAAC '97), Singapore, 17-19 December 1997. In Lecture Notes in Computer Science, 1997, v. 1350, p. 314-323-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/93143-
dc.description.abstractWe 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.languageeng-
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.titleAlgorithms for Finding Optimal Disjoint Paths Around a Rectangle-
dc.typeConference_Paper-
dc.identifier.emailChin, FYL: chin@cs.hku.hk-
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.doi10.1007/3-540-63890-3_34-
dc.identifier.scopuseid_2-s2.0-84958043739-
dc.identifier.hkuros31088-
dc.identifier.volume1350-
dc.identifier.spage314-
dc.identifier.epage323-
dc.publisher.placeGermany-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats