✦ LIBER ✦

Linear time algorithms for two disjoint paths problems on directed acyclic graphs

✍ Scribed by Tholey, Torsten

Book ID: 119375422
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 646 KB
Volume: 465
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2012.09.025

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Parameterized Tractability of Edge-Disjo

Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs

✍ Slivkins, Aleksandrs 📂 Article 📅 2010 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 229 KB

A linear time algorithm for the induced

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

✍ Ken-ichi Kawarabayashi; Yusuke Kobayashi 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 259 KB

A linear-time algorithm for edge-disjoin

A linear-time algorithm for edge-disjoint paths in planar graphs

✍ Dorothea Wagner; Karsten Weihe 📂 Article 📅 1995 🏛 Springer-Verlag 🌐 English ⚖ 1007 KB

Improved algorithms for finding length-b

Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph

✍ Chih-Chiang Yu; Chien-Hsin Lin; Biing-Feng Wang 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Linear algorithm for optimal path cover

Linear algorithm for optimal path cover problem on interval graphs

✍ Srinivasa Rao Arikati; C. Pandu Rangan 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 412 KB

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