English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Breaking the O(n^2.5) Deterministic Time Barrier for Undirected Unit-capacity Maximum Flow

Duan, R. (2013). Breaking the O(n^2.5) Deterministic Time Barrier for Undirected Unit-capacity Maximum Flow. In S. Khanna (Ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1171-1179). Philadelphia, PA: SIAM. doi:10.1137/1.9781611973105.84.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-7909-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A3FF-8
Genre: Conference Paper
Latex : Breaking the O(n^{2.5}) Deterministic Time Barrier for Undirected Unit-capacity Maximum Flow

Files

show Files
hide Files
:
max-flow2.pdf (Any fulltext), 178KB
 
File Permalink:
-
Name:
max-flow2.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Duan, Ran1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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≤q 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).

Details

show
hide
Language(s): eng - English
 Dates: 2013-012013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Duan2013
DOI: 10.1137/1.9781611973105.84
Other: Local-ID: BFE7035295CDA850C1257AD900645A84-Duan2013
 Degree: -

Event

show
hide
Title: Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
Place of Event: New Orleans, LA, USA
Start-/End Date: 2013-01-06 - 2013-01-08

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
  Abbreviation : SODA 2013
Source Genre: Proceedings
 Creator(s):
Khanna, Sanjeev1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1171 - 1179 Identifier: ISBN: 978-1-61197-251-1