๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A linear time algorithm for the induced disjoint paths problem in planar graphs

โœ Scribed by Ken-ichi Kawarabayashi; Yusuke Kobayashi

Book ID
113698491
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
259 KB
Volume
78
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A simple linear algorithm for the edge-d
A simple linear algorithm for the edge-disjoint (s, t)-paths problem in undirected planar graphs
โœ Laurent Coupry ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 400 KB

Let G = (v!E) be an undirected planar graph, and s, 1 E V, s # f. We present a linear algorithm to compute a set of edge-disjoint (s, t)-paths of maximum cardinality in G. In other words, the problem is to find a maximum unit flow from s to r in a non-weighted graph. The main purpose is not to show

Edge-Disjoint (s, t)-Paths in Undir
Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time
โœ Karsten Weihe ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 279 KB

We consider the following problem. Let G s V, E be an undirected planar graph and let s, t g V, s / t. The problem is to find a set of pairwise edge-disjoint paths in G, each connecting s with t, of maximum cardinality. In other words, the problem is to find a maximum unit flow from s to t. The fast