Hydras: complexity on general graphs and a subclass of trees

DOI10.1016/J.TCS.2016.05.037MaRDI QIDQ507535zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Hydras: directed hypergraphs and Horn formulas
• Hydras: directed hypergraphs and Horn formulas
• On the hydra number of disconnected graphs
• Hydra Games and Tree Ordinals
• scientific article; zbMATH DE number 4089568

Cites work

• scientific article; zbMATH DE number 4053069 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A decomposition method for CNF minimality proofs
• Hardness results for approximate pure Horn CNF formulae minimization
• Hydras: directed hypergraphs and Horn formulas
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimal Representation of Directed Hypergraphs
• On approximate Horn formula minimization
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• Unification as a complexity measure for logic programming

Cited in

(7)

• Approximating minimum representations of key Horn functions
• On the hydra number of disconnected graphs
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Unique key Horn functions
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• Hydras: directed hypergraphs and Horn formulas
• Hydras: directed hypergraphs and Horn formulas

Describes a project that uses

Uses Software

• Ltur

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

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