Linear connectivity problems in directed hypergraphs
From MaRDI portal
Publication:1029330
DOI10.1016/j.tcs.2009.02.038zbMath1172.68050MaRDI QIDQ1029330
Publication date: 10 July 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.038
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Directed hypergraphs: introduction and fundamental algorithms -- a survey, On the complexity of strongly connected components in directed hypergraphs, Linear time analysis of properties of conflict-free and general Petri nets, Flow hypergraph reducibility, Directed hypergraphs and Horn minimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On-line algorithms for satisfiability problems with uncertainty
- The complexity of facets (and some facets of complexity)
- The complexity of combinatorial problems with succinct input representation
- Space-bounded reducibility among combinatorial problems
- The polynomial-time hierarchy
- A generalization of Dijkstra's algorithm
- Complete sets and the polynomial-time hierarchy
- On the cyclomatic number of a hypergraph
- Partially dynamic maintenance of minimum weight hyperpaths
- Directed hypergraphs and applications
- Graph Algorithms for Functional Dependency Manipulation
- How to share a secret
- Succinct representations of graphs
- Minimal Representation of Directed Hypergraphs
- New problems complete for nondeterministic log space
- A note on succinct representations of graphs
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- Reducibility among Combinatorial Problems
