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, 725-736 p.Conference 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. 725-736 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9134
Keyword [en]
Dynamic graph algorithms, reachability
National Category
Computer Science
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: 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: 2015-07-15Bibliographically approved

Open Access in DiVA

No full text

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 Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 54 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