Change search
CiteExportLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:kth:diva-165849DOI: 10.1007/978-3-662-47672-7_59Scopus 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

Other links

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
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
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