Average case analysis of fully dynamic reachability for directed graphs

DOI10.1051/ITA/1996300403051MaRDI QIDQ3124401zbMATH OpenOpenAlexFDO

Authors Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spaccamela

Publication date 6 May 1997

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92539

zbMATH Keywords

directed graph

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Average case analysis of fully dynamic connectivity for directed graphs
• Average-case analysis of dynamic graph algorithms
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• scientific article; zbMATH DE number 910887
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Reachability Problems on Directed Graphs
• Dynamic complexity of directed reachability and other problems
• Fault tolerant reachability for directed graphs

Cites work

• Amortized efficiency of a path retrieval data structure
• Average case analysis of fully dynamic reachability for directed graphs
• Finding paths and deleting edges in directed acyclic graphs
• Generating quasi-random sequences from semi-random sources
• scientific article; zbMATH DE number 432745 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3900809 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• scientific article; zbMATH DE number 4083002 (Why is no real title available?)
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• Incremental algorithms for minimal length paths
• Linear expected-time algorithms for connectivity problems
• The thermistor: A problem in heat and current flow
• The transitive closure of a random digraph
• Worst-case Analysis of Set Union Algorithms

Cited in

(3)

• Average case analysis of fully dynamic reachability for directed graphs
• Average case analysis of fully dynamic connectivity for directed graphs
• Average-case analysis of best-first search in two representative directed acyclic graphs

This page was built for publication: Average case analysis of fully dynamic reachability for directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3124401)