Hydras: directed hypergraphs and Horn formulas
From MaRDI portal
Publication:507537
DOI10.1016/j.tcs.2016.05.036zbMath1357.68151OpenAlexW2480160089MaRDI QIDQ507537
Robert H. Sloan, György Turán, Despina Stasi
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.036
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Classical propositional logic (03B05) Directed graphs (digraphs), tournaments (05C20)
Related Items
Unique key Horn functions, Directed hypergraphs: introduction and fundamental algorithms -- a survey, On the hydra number of disconnected graphs, Approximating Minimum Representations of Key Horn Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Construction and learnability of canonical Horn formulas
- The total interval number of a tree and the Hamiltonian completion number of its line graph
- The total interval number of a graph
- The edge Hamiltonian path problem is NP-complete
- Horn functions and their DNFs
- Learning conjunctions of Horn clauses
- Optimal compression of propositional Horn knowledge bases: Complexity and approximation
- A linear algorithm for the Hamiltonian completion number of the line graph of a tree
- Hardness results for approximate pure Horn CNF formulae minimization
- On double and multiple interval graphs
- On Approximate Horn Formula Minimization
- Minimal Representation of Directed Hypergraphs
- Extremal Values of the Interval Number of a Graph
- The Total Interval Number of a Graph II: Trees and Complexity
- Hydras: Directed Hypergraphs and Horn Formulas
- Trees with Hamiltonian square