Linear connectivity problems in directed hypergraphs

DOI10.1016/j.tcs.2009.02.038zbMath1172.68050MaRDI QIDQ1029330

Rahul Tripathi, Mayur Thakur

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

zbMATH Keywords

directed hypergraphs; complexity classes; cyclomatic number of hypergraphs; directed hyperpaths

Mathematics Subject Classification ID

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

Linear time analysis of properties of conflict-free and general Petri nets, Flow hypergraph reducibility

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item