On the complexity of strongly connected components in directed hypergraphs
From MaRDI portal
Publication:517789
DOI10.1007/s00453-012-9729-0zbMath1360.68485arXiv1112.1444OpenAlexW2029313157MaRDI QIDQ517789
Publication date: 27 March 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.1444
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (7)
Whitney's connectivity inequalities for directed hypergraphs ⋮ Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope ⋮ Fuzzy logic programs as hypergraphs. Termination results ⋮ Computing the vertices of tropical polyhedra using directed hypergraphs ⋮ Strongly connected multivariate digraphs ⋮ A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors ⋮ Ergodicity conditions for zero-sum games
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Path-based depth-first search for strong and biconnected components
- Reachability analysis for timed automata using max-plus algebra
- A simple sub-quadratic algorithm for computing the subset partial order
- Opportunistic algorithms for eliminating supersets
- Dynamic maintenance of directed hypergraphs
- Computing the subset partial order for dense families of sets
- On finding hypercycles in chemical reaction networks
- Linear connectivity problems in directed hypergraphs
- A fast bit-parallel algorithm for computing the subset partial order
- Finding extremal sets in less than quadratic time
- Max Horn SAT and the minimum cut problem in directed hypergraphs
- A directed hypergraph model for random time dependent shortest paths
- Directed hypergraphs and applications
- A new algorithm for the propositional satisfiability problem
- Algorithms for dense graphs and networks on the random access computer
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks
- Graph Algorithms for Functional Dependency Manipulation
- Structure Theorems for Optimum Hyperpaths in Directed Hypergraphs
- Inferring Min and Max Invariants Using Max-Plus Polyhedra
- Minimal Representation of Directed Hypergraphs
- On-line algorithms for polynomially solvable satisfiability problems
- On Finding the Maxima of a Set of Vectors
- The Perron-Frobenius theorem for homogeneous, monotone functions
- On Computing the Subset Graph of a Collection of Sets
- Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
- Theory and Applications of Satisfiability Testing
- The Transitive Reduction of a Directed Graph
- Depth-First Search and Linear Graph Algorithms
- Simple linear-time algorithms for minimal fixed points
This page was built for publication: On the complexity of strongly connected components in directed hypergraphs
