MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Duan, Randblp
Editor(s):
BibTeX cite key*:
Duan2013
Title, Booktitle
Title*:
Breaking the $O(n^2.5)$ Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow
Booktitle*:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da13/
Downloading URL:
Event Address*:
New Orleans, Louisiana, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 January 2013
Event End Date:
8 January 2013
Publisher
Name*:
ACM-SIAM
URL:
http://www.siam.org/
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
6B
Number:
Month:
January
Pages:
1171-1179
Year*:
2013
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
This paper gives the first $o(n^{2.5})$ deterministic algorithm for the maximum flow problem in any undirected unit-capacity graph with no parallel edges. In an $n$-vertex, $m$-edge graph with maximum flow value $v$, our running time is $\tilde{O}(n^{9/4}v^{1/8})=\tilde{O}(n^{2.375})$. Note that $v\leq n$ for simple unit-capacity graphs. The previous deterministic algorithms [Karger and Levine 1998] achieve $O(m+nv^{3/2})$ and $O(nm^{2/3}v^{1/6})$ time bound, which are both $O(n^{2.5})$ for dense simple graphs and $v=\Theta(n)$.
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Duan2013,
AUTHOR = {Duan, Ran},
TITLE = {Breaking the $O(n^{2.5})$ Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow},
BOOKTITLE = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)},
PUBLISHER = {ACM-SIAM},
YEAR = {2013},
VOLUME = {6B},
PAGES = {1171--1179},
ADDRESS = {New Orleans, Louisiana, USA},
MONTH = {January},
}


Entry last modified by Stephanie Müller, 02/17/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/19/2012 07:16:07 PM
Revision
1.
0.


Editor
Stephanie Müller
Ran Duan


Edit Date
04.02.2013 14:30:00
12/19/2012 07:16:07 PM