首页 | 本学科首页   官方微博 | 高级检索  
     


A linear-time algorithm for edge-disjoint paths in planar graphs
Authors:Dorothea Wagner  Karsten Weihe
Affiliation:1. Informatik, Universit?t Konstanz, 78434, Konstanz, Germany
2. Informatik, Universit?t Konstanz, 78434, Konstanz, Germany
Abstract:In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n 5/3(loglogn)1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.
Keywords:05 C 85  68 Q 35
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号