Hydras: directed hypergraphs and Horn formulas

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

zbMATH Keywords

hydradirected hypergraphsHorn formulasHorn minimizationhydra number

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Classical propositional logic (03B05) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

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

This page was built for publication: Hydras: directed hypergraphs and Horn formulas