On hypergraph acyclicity and graph chordality
From MaRDI portal
(Redirected from Publication:1114449)
Concepts of acyclicity in hypergraphs and chordality in graphs are related by showing that a hierarchy of well-studied classes of chordal graphs corresponds to the hierarchy of classes of acyclic hypergraphs studied in relational database theory [\textit{R. Fagin}, J. Assoc. Comput. Mach. 30, 514-550 (1983; Zbl 0624.68088)].
Recommendations
- Degrees of acyclicity for hypergraphs and relational database schemes
- scientific article; zbMATH DE number 859448
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- On axioms constituting the foundation of hypergraph theory
- On the notion of cycles in hypergraphs
Cites work
- A Characterization of Certain Ptolemaic Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A characterization of ptolemaic graphs
- A characterization of totally balanced hypergraphs
- Characterizations of strongly chordal graphs
- Characterizations of totally balanced matrices
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- Connections in acyclic hypergraphs
- Degrees of acyclicity for hypergraphs and relational database schemes
- Distance-hereditary graphs
- scientific article; zbMATH DE number 3884212 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- Hypergraphs with no special cycles
- Hypergraphs without a large star
- On metric properties of certain clique graphs
- On the Desirability of Acyclic Database Schemes
- Parallel concepts in graph theory
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Steiner trees, connected domination and strongly chordal graphs
- Syntactic Characterization of Tree Database Schemas
- Testing the universal instance assumption
- Tree queries
Cited in
(19)- Laminar structure of ptolemaic graphs with applications
- Canonical and monophonic convexities in hypergraphs
- A fast algorithm for query optimization in universal-relation databases
- The parallel solution of domination problems on chordal and strongly chordal graphs
- Incidence graphs of biacyclic hypergraphs
- On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
- A formal context for closures of acyclic hypergraphs
- On the Galois lattice of bipartite distance hereditary graphs
- Further study on sizes of acyclic hypergraphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Equivalence between hypergraph convexities
- Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
- Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
- Dually chordal graphs
- On some partial line graphs of a hypergraph and the associated matroid
- Connections in acyclic hypergraphs
- Clique graphs and Helly graphs
This page was built for publication: On hypergraph acyclicity and graph chordality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114449)
