Hydras: complexity on general graphs and a subclass of trees

DOI10.1016/j.tcs.2016.05.037zbMath1357.68150OpenAlexW2415322127WikidataQ62044319 ScholiaQ62044319MaRDI QIDQ507535

Petr Kučera

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.037

zbMATH Keywords

caterpillarHorn minimizationHorn CNFhydra formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical propositional logic (03B05)

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

Uses Software

• Ltur

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition method for CNF minimality proofs
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Hardness results for approximate pure Horn CNF formulae minimization
• On Approximate Horn Formula Minimization
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimal Representation of Directed Hypergraphs
• Unification as a complexity measure for logic programming
• Hydras: Directed Hypergraphs and Horn Formulas

This page was built for publication: Hydras: complexity on general graphs and a subclass of trees