Hydras: directed hypergraphs and Horn formulas

DOI10.1016/J.TCS.2016.05.036MaRDI QIDQ507537zbMATH OpenOpenAlexFDO

Authors R. H. Sloan, Despina Stasi, Gy. Turán

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

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

Recommendations

• Hydras: directed hypergraphs and Horn formulas
• On the hydra number of disconnected graphs
• Hydras: complexity on general graphs and a subclass of trees
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• Random Horn formulas and propagation connectivity for directed hypergraphs

Cites work

• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• Construction and learnability of canonical Horn formulas
• Extremal Values of the Interval Number of a Graph
• Hardness results for approximate pure Horn CNF formulae minimization
• Horn functions and their DNFs
• Hydras: directed hypergraphs and Horn formulas
• Learning conjunctions of Horn clauses
• Minimal Representation of Directed Hypergraphs
• On approximate Horn formula minimization
• On double and multiple interval graphs
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The Total Interval Number of a Graph II: Trees and Complexity
• The edge Hamiltonian path problem is NP-complete
• The total interval number of a graph
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• Trees with Hamiltonian square

Cited in

(7)

• On the hydra number of disconnected graphs
• Directed hypergraphs and Horn minimization
• Approximating minimum representations of key Horn functions
• Unique key Horn functions
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• Hydras: complexity on general graphs and a subclass of trees
• Hydras: directed hypergraphs and Horn formulas

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507537)