you're reading...

Reading group meeting: Maximum flows in one-crossing-minor-free graphs

Time: 1:00pm Tuesday 9 July

Location: SIT 402

Speaker: Karsten Klein, University of Sydney

Paper: “Maximum flows in one-crossing-minor-free graphs” by Chambers and Eppstein


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 K 3,3-minor-free graphs and directed K 5-minor-free graphs can be computed in O(nlogn) time without additional assumptions.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: