Hydras: directed hypergraphs and Horn formulas

DOI10.1016/J.TCS.2016.05.036zbMATH Open1357.68151OpenAlexW2480160089MaRDI QIDQ507537FDOQ507537

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

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

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)

Cites Work

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

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)