Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4468-2675
2015 (English)In: Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Springer Berlin/Heidelberg, 2015, p. 725-736Conference paper, Published paper (Refereed)
##### Abstract [en]

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn)  total update time, where m  is the number of edges and n  is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m  vs. n  trade-off. For the case of m=Θ(n 1.5 )  the running time is O(n 2.47 )  , just barely below mn=Θ(n 2.5 )  . In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of O ~ (min(m 7/6 n 2/3 ,m 3/4 n 5/4+o(1) ,m 2/3 n 4/3+o(1) +m 3/7 n 12/7+o(1) )) . This gives, e.g., O(n 2.36 )  for the notorious case m=Θ(n 1.5 ) . We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.

##### Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. p. 725-736
##### Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9134
##### Keyword [en]
Dynamic graph algorithms, reachability
##### National Category
Computer Sciences
##### Identifiers
Scopus ID: 2-s2.0-84950161208ISBN: 978-3-662-47672-7 (print)OAI: oai:DiVA.org:kth-165849DiVA, id: diva2:808917
##### Conference
The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), 6-10 July 2015, Kyoto, Japan
##### Note

QC 20150715

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2018-01-11Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Publisher's full textScopusThe final publication is available at www.springerlink.com

#### Authority records BETA

Nanongkai, Danupon

#### Search in DiVA

##### By author/editor
Nanongkai, Danupon
##### By organisation
Theoretical Computer Science, TCS
##### On the subject
Computer Sciences

doi
isbn
urn-nbn

#### Altmetric score

doi
isbn
urn-nbn
Total: 57 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
v. 2.33.0
| | | |