Geodesic
Flows in One-Crossing-Minor-Free Graphs
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 201-220.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study the maximum flow problem in directed H-minor-free graphs where H can be drawn in the plane with one crossing. If a structural decomposition of the graph as a clique-sum of planar graphs and graphs of constant complexity is given, we show that a maximum flow can be computed in O(nlogn) time. In particular, maximum flows in directed K3,3-minor-free graphs and directed K5-minor-free graphs can be computed in O(nlogn) time without additional assumptions.
DOI : 10.7155/jgaa.00291
Keywords: maximum flows, minor free graphs, flow algorithms, 1-crossing minor free graphs 
@article{JGAA_2013_17_3_a2,
     author = {Erin Wolf Chambers and David Eppstein},
     title = {Flows in {One-Crossing-Minor-Free} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {201--220},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2013},
     doi = {10.7155/jgaa.00291},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00291/}
}
TY  - JOUR
AU  - Erin Wolf Chambers
AU  - David Eppstein
TI  - Flows in One-Crossing-Minor-Free Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 201
EP  - 220
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00291/
DO  - 10.7155/jgaa.00291
LA  - en
ID  - JGAA_2013_17_3_a2
ER  - 
%0 Journal Article
%A Erin Wolf Chambers
%A David Eppstein
%T Flows in One-Crossing-Minor-Free Graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 201-220
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00291/
%R 10.7155/jgaa.00291
%G en
%F JGAA_2013_17_3_a2
Erin Wolf Chambers; David Eppstein. Flows in One-Crossing-Minor-Free Graphs. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 201-220. doi : 10.7155/jgaa.00291. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00291/

Cité par Sources :