A truly symbolic linear-time algorithm for SCC decomposition

DOI10.1007/978-3-031-30820-8_22MaRDI QIDQ6536142zbMATH OpenFDO

Authors Casper Abild Larsen, Simon Meldahl Schmidt, Jesper Steensgaard, Anna Blume Jakobsen, Jaco van de Pol, Andreas Pavlogiannis

Publication date 5 April 2024

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-30820-8_22

zbMATH Keywords

colored graphsbinary decision diagramsstrongly connected components

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Nonnumerical algorithms (68W05) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Symbolic coloured SCC decomposition
• scientific article; zbMATH DE number 2079387
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• scientific article; zbMATH DE number 7566051
• Symbolic graphs: Linear solutions to connectivity related problems

Cites work

• scientific article; zbMATH DE number 1705167 (Why is no real title available?)
• scientific article; zbMATH DE number 3574936 (Why is no real title available?)
• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• scientific article; zbMATH DE number 1863179 (Why is no real title available?)
• scientific article; zbMATH DE number 1903365 (Why is no real title available?)
• scientific article; zbMATH DE number 2102708 (Why is no real title available?)
• scientific article; zbMATH DE number 7566051 (Why is no real title available?)
• A CTL* Model Checker for Petri Nets
• A new heuristic for bad cycle detection using BDDs
• A strong-connectivity algorithm and its applications in data flow analysis
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• Computing bottom SCCs symbolically using transition guided reduction
• Depth-First Search and Linear Graph Algorithms
• Distributed algorithms for SCC decomposition
• Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
• Lower bounds for symbolic computation on graphs: strongly connected components, liveness, safety, and diameter
• Model checking with strong fairness
• Tools and Algorithms for the Construction and Analysis of Systems

This page was built for publication: A truly symbolic linear-time algorithm for SCC decomposition

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