Minimal Representation of Directed Hypergraphs
From MaRDI portal
Publication:3738576
DOI10.1137/0215029zbMath0602.68056OpenAlexW2061936891MaRDI QIDQ3738576
Alessandro D'Atri, Domenico Saccà, Giorgio Ausiello
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215029
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Optimal covers in the relational database model ⋮ Amortized efficiency of a path retrieval data structure ⋮ A hypergraph model for constraint logic programming and applications to bus drivers' scheduling ⋮ Attribute-incremental construction of the canonical implication basis ⋮ Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Redundancy in logic. III: Non-monotonic reasoning ⋮ Directed hypergraphs and Horn minimization ⋮ Dynamic maintenance of the transitive closure in disjunctive graphs ⋮ A decomposition method for CNF minimality proofs ⋮ Unique key Horn functions ⋮ On vertex independence number of uniform hypergraphs ⋮ Boolean functions with a simple certificate for CNF complexity ⋮ Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements ⋮ Finding the \(K\) best policies in a finite-horizon Markov decision process ⋮ Dynamic maintenance of directed hypergraphs ⋮ Properties of Switch-List Representations of Boolean Functions ⋮ Bidual Horn functions and extensions ⋮ Boolean functions with long prime implicants ⋮ Algorithms for computing minimal equivalent subformulas ⋮ Redundancy in logic. I: CNF propositional formulae ⋮ On-line algorithms for satisfiability problems with uncertainty ⋮ On-line algorithms for satisfiability problems with uncertainty ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Directed hypergraphs: introduction and fundamental algorithms -- a survey ⋮ Succinctness and tractability of closure operator representations ⋮ Hydras: complexity on general graphs and a subclass of trees ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ Recognition of tractable DNFs representable by a constant number of intervals ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ A subclass of Horn CNFs optimally compressible in polynomial time ⋮ Exclusive and essential sets of implicates of Boolean functions ⋮ Primitive tensors and directed hypergraphs ⋮ Unnamed Item ⋮ Dynamic algorithms for classes of constraint satisfaction problems ⋮ Partially dynamic maintenance of minimum weight hyperpaths ⋮ The complexity of arc-colorings for directed hypergraphs ⋮ Extension and equivalence problems for clause minimal formulae ⋮ Autonomous Sets – A Method for Hypergraph Decomposition with Applications in Database Theory ⋮ The complexity of arc-colorings for directed hypergraphs ⋮ Directed hypergraphs and applications ⋮ On implicational bases of closure systems with unique critical sets. ⋮ Linear connectivity problems in directed hypergraphs ⋮ Disjoint essential sets of implicates of a CQ Horn function ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ On the hydra number of disconnected graphs ⋮ Approximating Minimum Representations of Key Horn Functions
