Symbolic graphs: Linear solutions to connectivity related problems

DOI10.1007/s00453-007-9079-5zbMath1203.68039MaRDI QIDQ2471809

Raffaella Gentilini, Carla Piazza, Alberto Policriti

Publication date: 18 February 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9079-5

zbMATH Keywords

Model checking; Ordered binary decision diagrams; Biconnected components; Strongly connected components; Massive graphs

Mathematics Subject Classification ID

68P05: Data structures

Related Items

Unnamed Item, Fine-grained complexity lower bounds for problems in computer aided verification, On the OBDD representation of some graph classes, On symbolic OBDD-based algorithms for the minimum spanning tree problem, On efficient implicit OBDD-based algorithms for maximal matchings, Implicit computation of maximum bipartite matchings by sublinear functional operations, Larger lower bounds on the OBDD complexity of integer multiplication, On the size of (generalized) OBDDs for threshold functions, Randomized OBDD-based graph algorithms, Exponential space complexity for OBDD-based reachability analysis, Symbolic coloured SCC decomposition, Priority functions for the approximation of the metric TSP, Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations, Randomized OBDD-Based Graph Algorithms, On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem, Larger Lower Bounds on the OBDD Complexity of Integer Multiplication

Uses Software

• CUDD
• Algorithm 447
• VIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bisimulation minimization and symbolic model checking
• Symbolic model checking: \(10^{20}\) states and beyond
• Verification of reactive systems. Formal methods and algorithms.
• BDDs -- design, analysis, complexity, and applications.
• Binary decision diagrams in theory and practice
• The nonapproximability of OBDD minimization
• Testing language containment for \(\omega\)-automata using BDDs
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• Graph-Based Algorithms for Boolean Function Manipulation
• Binary Decision Diagrams
• Improving the variable ordering of OBDDs is NP-complete
• Algorithms and Computation
• Mathematical Foundations of Computer Science 2003
• Depth-First Search and Linear Graph Algorithms
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation
• SOFSEM 2004: Theory and Practice of Computer Science