Symbolic graphs: Linear solutions to connectivity related problems

DOI10.1007/s00453-007-9079-5zbMath1203.68039OpenAlexW2125161077MaRDI 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 checkingOrdered binary decision diagramsBiconnected componentsStrongly connected componentsMassive graphs

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

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