File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/3-540-63890-3_34
- Scopus: eid_2-s2.0-84958043739
- Find via
Supplementary
-
Citations:
- Scopus: 0
- 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, 17-19 December 1997. In Lecture Notes in Computer Science, 1997, v. 1350, p. 314-323 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 | 2020 SCImago Journal Rankings: 0.249 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Chan, WT | - |
| dc.contributor.author | Chin, FYL | - |
| dc.date.accessioned | 2010-09-25T14:52:11Z | - |
| dc.date.available | 2010-09-25T14:52:11Z | - |
| dc.date.issued | 1997 | - |
| dc.identifier.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 | - |
| dc.identifier.issn | 0302-9743 | - |
| 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/3-540-63890-3_34 | - |
| dc.identifier.scopus | eid_2-s2.0-84958043739 | - |
| dc.identifier.hkuros | 31088 | - |
| dc.identifier.volume | 1350 | - |
| dc.identifier.spage | 314 | - |
| dc.identifier.epage | 323 | - |
| dc.publisher.place | Germany | - |
| dc.identifier.issnl | 0302-9743 | - |