Symbolic graphs: Linear solutions to connectivity related problems
From MaRDI portal
Publication:2471809
DOI10.1007/S00453-007-9079-5zbMATH Open1203.68039OpenAlexW2125161077MaRDI QIDQ2471809FDOQ2471809
Authors: 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
Recommendations
Model checkingOrdered binary decision diagramsBiconnected componentsStrongly connected componentsMassive graphs
Cites Work
- Title not available (Why is that?)
- Graph-Based Algorithms for Boolean Function Manipulation
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Symbolic model checking: \(10^{20}\) states and beyond
- An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
- Binary Decision Diagrams
- Title not available (Why is that?)
- SOFSEM 2004: Theory and Practice of Computer Science
- Improving the variable ordering of OBDDs is NP-complete
- Title not available (Why is that?)
- BDDs -- design, analysis, complexity, and applications.
- Title not available (Why is that?)
- Algorithms and Computation
- Mathematical Foundations of Computer Science 2003
- Graph-Theoretic Concepts in Computer Science
- Bisimulation minimization and symbolic model checking
- Binary decision diagrams in theory and practice
- The nonapproximability of OBDD minimization
- Title not available (Why is that?)
- Verification of reactive systems. Formal methods and algorithms.
- Title not available (Why is that?)
- Algorithms and Computation
- Testing language containment for \(\omega\)-automata using BDDs
Cited In (27)
- How to determine the solvability of bond graph linear junction structures
- Title not available (Why is that?)
- Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
- Larger lower bounds on the OBDD complexity of integer multiplication
- Symbolic coloured SCC decomposition
- Lower bounds for symbolic computation on graphs: strongly connected components, liveness, safety, and diameter
- Title not available (Why is that?)
- Fine-grained complexity lower bounds for problems in computer aided verification
- Mathematical Foundations of Computer Science 2003
- Title not available (Why is that?)
- On the OBDD representation of some graph classes
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- On efficient implicit OBDD-based algorithms for maximal matchings
- Representation of graphs and its algorithms based on BDD
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- Exponential space complexity for OBDD-based reachability analysis
- Randomized OBDD-based graph algorithms
- Randomized OBDD-based graph algorithms
- An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
- A truly symbolic linear-time algorithm for SCC decomposition
- Algorithms and Computation
- On the size of (generalized) OBDDs for threshold functions
- Graph-Theoretic Concepts in Computer Science
- Priority functions for the approximation of the metric TSP
- Symbolic topological sorting with OBDDs
- On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
Uses Software
This page was built for publication: Symbolic graphs: Linear solutions to connectivity related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2471809)
