On the complexity of strongly connected components in directed hypergraphs

DOI10.1007/S00453-012-9729-0zbMath1360.68485arXiv1112.1444OpenAlexW2029313157MaRDI QIDQ517789

Xavier Allamigeon

Publication date: 27 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.1444

zbMATH Keywords

directed hypergraphsstrongly connected componentsminimal set problemsubset partial order

Mathematics Subject Classification ID

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

• TPLib

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