Graph Theory

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture   Can the approximation ratio $ O(\sqrt{n}) $ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $ \mathcal{APX} $-hardness?

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

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ($ \diamond $)   Let $ L $ be a simple regular ordered $ 2 $-stage graph. Suppose that the graph $ L^m $ is externally connected, for some $ m\ge1 $. Then the graph $ L^{2m} $ is rearrangeable.

Keywords:

Posted by Vadim Lioubimov
updated April 17th, 2010
add new comment | 3 attachments