Linear connectivity problems in directed hypergraphs

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

Mayur Thakur, Rahul Tripathi

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 hypergraphscomplexity classescyclomatic number of hypergraphsdirected hyperpaths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Directed hypergraphs and Horn minimization ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ Fuzzy logic programs as hypergraphs. Termination results ⋮ Finding \((s,d)\)-hypernetworks in F-hypergraphs is NP-hard ⋮ Persistent hyperdigraph homology and persistent hyperdigraph Laplacians ⋮ Optimal directed hypergraph traversal with ant-colony optimisation ⋮ Flow hypergraph reducibility ⋮ Directed hypergraphs: introduction and fundamental algorithms -- a survey ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ α-Derivable digraphs and its application in wireless sensor networking

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

This page was built for publication: Linear connectivity problems in directed hypergraphs