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 条
  • [41] Using Bidirectional Search to Compute Optimal Shortest Paths over Multi-Weight Graphs
    Ma, Hui
    Liang, Ruishi
    PROCEEDINGS OF 2013 INTERNATIONAL CONFERENCE ON INFORMATION SCIENCE AND CLOUD COMPUTING COMPANION (ISCC-C), 2014, : 66 - 71
  • [42] Bundling all shortest paths
    Debski, Michal
    Junosza-Szaniawski, Konstanty
    Lonc, Zbigniew
    DISCRETE APPLIED MATHEMATICS, 2020, 277 : 82 - 91
  • [43] The complexity of rerouting shortest paths
    Bonsma, Paul
    THEORETICAL COMPUTER SCIENCE, 2013, 510 : 1 - 12
  • [44] Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs
    Baswana, Surender
    Khanna, Neelesh
    ALGORITHMICA, 2013, 66 (01) : 18 - 50
  • [45] Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs
    Surender Baswana
    Neelesh Khanna
    Algorithmica, 2013, 66 : 18 - 50
  • [46] Hardware Architecture for Finding Shortest Paths
    Sridharan, K.
    Priya, T. K.
    Kumar, P. Rajesh
    TENCON 2009 - 2009 IEEE REGION 10 CONFERENCE, VOLS 1-4, 2009, : 301 - +
  • [47] The number of shortest paths in the arrangement graph
    Cheng, Eddie
    Grossman, Jerrold W.
    Qiu, Ke
    Shen, Zhizhang
    INFORMATION SCIENCES, 2013, 240 : 191 - 204
  • [48] Improved algorithms for dynamic shortest paths
    Djidjev, HN
    Pantziou, GE
    Zaroliagis, CD
    ALGORITHMICA, 2000, 28 (04) : 367 - 389
  • [49] Total Curvature and Spiralling Shortest Paths
    Imre Bárány
    Krystyna Kuperberg
    Tudor Zamfirescu
    Discrete & Computational Geometry, 2003, 30 : 167 - 176
  • [50] Total curvature and spiralling shortest paths
    Bárány, I
    Kuperberg, K
    Zamfirescu, T
    DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (02) : 167 - 176
12345