Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor

Author(s):

Duan, Ran
dblp


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

URL of the conference:

http://www.siam.org/meetings/da13/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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