Average case analysis of fully dynamic connectivity for directed graphs

DOI10.1007/3-540-57899-4_43zbMath1528.68265OpenAlexW1550385021MaRDI QIDQ6184396

Unnamed Author, Paola Alimonti, Xavier Messeguer, Stefano Leonardi

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57899-4_43

zbMATH Keywords

directed graphrandom graphtransitive closuredynamic graphconnectivity query

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20)

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
• Incremental convex planarity testing
• The transitive closure of a random digraph
• Worst-case Analysis of Set Union Algorithms
• Linear expected-time algorithms for connectivity problems
• Incremental algorithms for minimal length paths
• Maintenance of triconnected components of graphs
• 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 connectivity for directed graphs