Average case analysis of fully dynamic reachability for directed graphs

DOI10.1051/ita/1996300403051zbMath0876.68080OpenAlexW14010256MaRDI QIDQ3124401

Paola Alimonti, Alberto Marchetti-Spaccamela, Stefano Leonardi

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

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

Related Items (1)

Average case analysis of fully dynamic reachability for directed graphs

Cites Work

• Generating quasi-random sequences from semi-random sources
• Amortized efficiency of a path retrieval data structure
• Finding paths and deleting edges in directed acyclic graphs
• Average case analysis of fully dynamic reachability for directed graphs
• The transitive closure of a random digraph
• Worst-case Analysis of Set Union Algorithms
• The thermistor: A problem in heat and current flow
• Linear expected-time algorithms for connectivity problems
• Incremental algorithms for minimal length paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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