Shortest noncrossing paths in plane graphs

被引：13
|
作者：
Takahashi, JY [1 ]
Suzuki, H [1 ]
Nishizeki, T [1 ]
机构：
[1] TOHOKU UNIV, GRAD SCH INFORMAT SCI, SENDAI, MIYAGI 98077, JAPAN
来源：
ALGORITHMICA | 1996年 / 16卷 / 03期
关键词：
noncrossing paths; shortest path; plane graphs; single-layer routing; VLSI;
D O I：
10.1007/BF01955681
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Let G be an undirected plane graph with nonnegative edge length, and let k terminal pairs Lie on two specified face boundaries. This paper presents an algorithm for finding k ''noncrossing paths'' in G, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in time O(n log n) where n is the number of vertices in G and k is an arbitrary integer.
引用
收藏
页码：339 / 357
页数：19
相关论文
共 50 条
  • [1] ALGORITHMS FOR FINDING NONCROSSING PATHS WITH MINIMUM TOTAL LENGTH IN PLANE GRAPHS
    TAKAHASHI, J
    SUZUKI, H
    NISHIZEKI, T
    ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, 1995, 78 (04): : 1 - 15
  • [2] Shortest Paths on Evolving Graphs
    Zou, Yiming
    Zeng, Gang
    Wang, Yuyi
    Liu, Xingwu
    Sun, Xiaoming
    Zhang, Jialin
    Li, Qiang
    COMPUTATIONAL SOCIAL NETWORKS, CSONET 2016, 2016, 9795 : 1 - 13
  • [3] Shortest Paths in Euclidean Graphs
    Sedgewick, Robert
    Vitter, Jeffrey Scott
    ALGORITHMICA, 1986, 1 (1-4) : 31 - 48
  • [4] Shortest paths in Sierpinski graphs
    Xue, Bing
    Zuo, Liancui
    Wang, Guanghui
    Li, Guojun
    DISCRETE APPLIED MATHEMATICS, 2014, 162 : 314 - 321
  • [5] Shortest paths of butterfly graphs
    Hwang, SC
    Chen, GH
    INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-V, PROCEEDINGS, 1999, : 2195 - 2199
  • [6] Reconfiguring Shortest Paths in Graphs
    Gajjar, Kshitij
    Jha, Agastya Vibhuti
    Kumar, Manish
    Lahiri, Abhiruk
    ALGORITHMICA, 2024, 86 (10) : 3309 - 3338
  • [7] SHORTEST PATHS ANONYMIZATION ON WEIGHTED GRAPHS
    Wang, Shyue-Liang
    Tsai, Yu-Chuan
    Kao, Hung-Yu
    Ting, I-Hsien
    Hong, Tzung-Pei
    INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING, 2013, 23 (01) : 65 - 79
  • [8] Rerouting shortest paths in planar graphs
    Bonsma, Paul
    DISCRETE APPLIED MATHEMATICS, 2017, 231 : 95 - 112
  • [9] On shortest disjoint paths in planar graphs
    Kobayashi, Yusuke
    Sommer, Christian
    DISCRETE OPTIMIZATION, 2010, 7 (04) : 234 - 245
  • [10] Approximate shortest paths in weighted graphs
    Yuster, Raphael
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (02) : 632 - 637
12345