
Disjoint paths
Kriesell's Conjecture ★★
Author(s): Kriesell
Conjecture Let
be a graph and let
such that for any pair
there are
edge-disjoint paths from
to
in
. Then
contains
edge-disjoint trees, each of which contains
.










Keywords: Disjoint paths; edge-connectivity; spanning trees
Approximation Ratio for Maximum Edge Disjoint Paths problem ★★
Author(s): Bentz
Conjecture Can the approximation ratio
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than
-hardness?


Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm
