English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  A lower bound for the nondeterministic space complexity of contextfree recognition

Cheriyan, J., Hagerup, T., & Mehlhorn, K.(1991). A lower bound for the nondeterministic space complexity of contextfree recognition (MPI-I-91-115). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7B1A-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-9515-3
Genre: Report

Files

show Files
hide Files
:
MPI-I-91-115.pdf (Any fulltext), 3MB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-002D-9506-7
Name:
MPI-I-91-115.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Cheriyan, Joseph1, Author
Hagerup, Torben1, Author
Mehlhorn, Kurt2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We show that a maximum flow in a network with $n$ vertices can be computed deterministically in $O({{n^3}/{\log n}})$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3)$. The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n^{8/3}(\log n)^{4/3})$, in contrast with $\Omega(nm)$ flow operations for all previous algorithms, where $m$ denotes the number of edges in the network. A randomized version of our algorithm executes $O(n^{3/2}m^{1/2}\log n+n^2(\log n)^2/ \log(2+n(\log n)^2/m))$ flow operations with high probability. For the special case in which all capacities are integers bounded by $U$, we show that a maximum flow can be computed

Details

show
hide
Language(s): eng - English
 Dates: 1991
 Publication Status: Issued
 Pages: 4 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-91-115
BibTex Citekey: AltGeffertMehlhorn91
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -