Some characterizations of and -acyclicity of hypergraphs

DOI10.1016/J.IPL.2012.05.005MaRDI QIDQ456059zbMATH OpenOpenAlexFDO

Authors David Duris

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.05.005

zbMATH Keywords

combinatorial problemsgraph algorithmshypergraph acyclicity

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 1135725
• On -hyperellipticity of graphs
• scientific article; zbMATH DE number 4081615
• On hypergraph acyclicity and graph chordality
• On acyclic and cyclic hypergraphs
• scientific article; zbMATH DE number 4029622
• Counting minimal transversals of -acyclic hypergraphs
• scientific article; zbMATH DE number 3937210
• A note on -graphs

Cites work

• Degrees of acyclicity for hypergraphs and relational database schemes
• scientific article; zbMATH DE number 3683635 (Why is no real title available?)
• scientific article; zbMATH DE number 1756016 (Why is no real title available?)
• Hypertree decompositions and tractable queries
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On the complexity of database queries

Cited in

(11)

• Tractability beyond -acyclicity for conjunctive queries with negation and SAT
• A polyhedral study of lifted multicuts
• The multilinear polytope for acyclic hypergraphs
• On optimization problems in acyclic hypergraphs
• On the complexity of binary polynomial optimization over acyclic hypergraphs
• A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
• Transit functions and pyramid-like binary clustering systems
• On the cut-vertex and the interval transit functions of hypergraphs
• The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
• Enumeration of minimal hitting sets parameterized by treewidth
• A hybrid tractable class for non-binary CSPs

This page was built for publication: Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs

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