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 条

[31] Non-crossing shortest paths lengths in planar graphs in linear time
Balzotti, Lorenzo
Franciosa, Paolo G.
DISCRETE APPLIED MATHEMATICS, 2024, 346 : 183 - 191
[32] Efficient parallel algorithms for computing all pair shortest paths in directed graphs
Yijie Han
V. Y. Pan
J. H. Reif
Algorithmica, 1997, 17 : 399 - 415
[33] FASTER ALGORITHMS FOR ALL-PAIRS APPROXIMATE SHORTEST PATHS IN UNDIRECTED GRAPHS
Baswana, Surender
Kavitha, Telikepalli
SIAM JOURNAL ON COMPUTING, 2010, 39 (07) : 2865 - 2896
[34] Shortest vertex-disjoint two-face paths in planar graphs
de Verdiere, Eric Colin
Schrijver, Alexander
STACS 2008: PROCEEDINGS OF THE 25TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 2008, : 181 - +
[35] The smallest pair of noncrossing paths in a rectilinear polygon
Yang, CD
Lee, DT
Wong, CK
IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (08) : 930 - 941
[36] New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Gutenberg, Maximilian Probst
Williams, Virginia Vassilevska
Wein, Nicole
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 153 - 166
[37] AN ALGORITHM FOR THE RANKING OF SHORTEST PATHS
AZEVEDO, JA
COSTA, MEOS
MADEIRA, JJERS
MARTINS, EQV
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 69 (01) : 97 - 106
[38] Computing shortest paths with uncertainty
Feder, Tomas
Motwani, Rajeev
O' Callaghan, Liadan
Olston, Chris
Panigrahy, Rina
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2007, 62 (01): : 1 - 18
[39] APPROXIMATE SHORTEST PATHS AVOIDING A FAILED VERTEX : OPTIMAL SIZE DATA STRUCTURES FOR UNWEIGHTED GRAPHS
Khanna, Neelesh
Baswana, Surender
27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 : 513 - 524
[40] AN AUCTION ALGORITHM FOR SHORTEST PATHS
Bertsekas, Dimitri P.
SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (04) : 425 - 447

← 1 2 3 4 5 →