Counting edges in a dag

DOI10.1007/3-540-62559-3_9MaRDI QIDQ6550536zbMATH OpenFDO

Authors Serafino Cicerone, Daniele Frigioni, Umberto Nanni, F. Pugliese

Publication date 5 June 2024

Full work available at URL https://doi.org/10.1007/3-540-62559-3_9

zbMATH Keywords

dominance relationshipdominator treeedge deletioninput modificationtransitive closure

Mathematics Subject Classification ID

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

Recommendations

• A uniform approach to semi-dynamic problems on digraphs
• Dynamic Dominators and Low-High Orders in DAGs
• A faster and simpler fully dynamic transitive closure
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• An experimental study of dynamic dominators

Cites work

• A fast algorithm for finding dominators in a flowgraph
• Algorithms of placing recovery points
• Amortized efficiency of a path retrieval data structure
• Computing dominators in parallel
• Fast Algorithms for Finding Nearest Common Ancestors
• Faster shortest-path algorithms for planar graphs
• Finding Dominators in Directed Graphs
• Finding paths and deleting edges in directed acyclic graphs
• scientific article; zbMATH DE number 4083002 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Incremental algorithms for minimal length paths
• Optimal algorithm for the nearest common dominator problem

Cited in

(1)

• Dynamic Dominators and Low-High Orders in DAGs

This page was built for publication: Counting edges in a dag

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