Flows in One-Crossing-Minor-Free Graphs

Details Flows in One-Crossing-Minor-Free Graphs Flows in One-Crossing-Minor-Free Graphs

2010-07-08

arxiv.org/abs/1007.1484v1

Computer Science

Data Structures and Algorithms

16 pages, 4 figures

Scientific paper

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(n log n) time. In particular, maximum flows in directed K_{3,3}-minor-free graphs and directed K_5-minor-free graphs can be computed in O(n log n) time without additional assumptions.

Affiliated with

Also associated with

No associations

Rating

Flows in One-Crossing-Minor-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Flows in One-Crossing-Minor-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flows in One-Crossing-Minor-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-644098