Dynamic complexity of directed reachability and other problems

DOI10.1007/978-3-662-43948-7_30MaRDI QIDQ5167755zbMATH OpenOpenAlexFDO

Authors Samir Datta, William Hesse, Raghav Kulkarni

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-43948-7_30

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Reachability is in DynFO
• Reachability is in DynFO
• Dynamic complexity of the Dyck reachability
• STACS 2005
• On the Quantifier-Free Dynamic Complexity of Reachability

Cited in

(14)

• Dyn-FO: A parallel, dynamic complexity class
• On the complexity of directed intersection representation of DAGs
• Dynamic complexity of expansion
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• On the Quantifier-Free Dynamic Complexity of Reachability
• Dynamic complexity of the Dyck reachability
• Average case analysis of fully dynamic reachability for directed graphs
• Reachability is in DynFO
• Reachability Problems on Directed Graphs
• Reachability is in DynFO
• Dynamic complexity of planar 3-connected graph isomorphism
• Derandomizing isolation in space-bounded settings
• Dynamic complexity of reachability: how many changes can we handle?
• Dynamic reachability in planar digraphs with one source and one sink

This page was built for publication: Dynamic complexity of directed reachability and other problems

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