Hydras: complexity on general graphs and a subclass of trees
DOI10.1016/J.TCS.2016.05.037zbMATH Open1357.68150OpenAlexW2415322127WikidataQ62044319 ScholiaQ62044319MaRDI QIDQ507535FDOQ507535
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical propositional logic (03B05)
Cites Work
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimal Representation of Directed Hypergraphs
- Title not available (Why is that?)
- 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
- Unification as a complexity measure for logic programming
- A decomposition method for CNF minimality proofs
- 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
- Approximating minimum representations of key Horn functions
- Unique key Horn functions
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- Directed hypergraphs: introduction and fundamental algorithms -- a survey
- Hydras: directed hypergraphs and Horn formulas
- Hydras: directed hypergraphs and Horn formulas
Uses Software
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)
