Fully Dynamic Transitive Closure in plane dags with one source and one sink

DOI10.1007/3-540-60313-1_144MaRDI QIDQ6102301zbMATH OpenOpenAlexFDO

Authors Thore Husfeldt

Publication date 8 May 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60313-1_144

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Dynamic Plane Transitive Closure
• A faster and simpler fully dynamic transitive closure
• scientific article; zbMATH DE number 2079364
• Speeding up dynamic transitive closure for bounded degree graphs
• Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier

Cites work

• A data structure for dynamic trees
• Algorithms for plane representations of acyclic digraphs
• Complexity models for incremental computation
• Dynamic maintenance of planar digraphs, with applications
• Dynamic reachability in planar digraphs with one source and one sink
• scientific article; zbMATH DE number 3904590 (Why is no real title available?)
• scientific article; zbMATH DE number 4060744 (Why is no real title available?)
• scientific article; zbMATH DE number 140481 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• scientific article; zbMATH DE number 1263186 (Why is no real title available?)
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 1263263 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• Improved data structures for fully dynamic biconnectivity
• Lower bounds for union-split-find related problems on random access machines
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Separator based sparsification for dynamic planar graph algorithms
• The design of dynamic data structures

Cited in

(3)

• Dynamic Plane Transitive Closure
• Counting edges in a dag
• Dynamic reachability in planar digraphs with one source and one sink

This page was built for publication: Fully Dynamic Transitive Closure in plane dags with one source and one sink

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