On hypergraph acyclicity and graph chordality
type: Item
instance of: scholarly article
title: On hypergraph acyclicity and graph chordality
zbMATH Open document ID: 0662.68111
DOI: 10.1016/0020-0190(88)90121-4
author: Alessandro D'Atri
author: Marina Moscarini
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4083039
zbMATH Keywords: acyclicity
zbMATH Keywords: hypergraphs
zbMATH Keywords: chordality
zbMATH Keywords: chordal graphs
zbMATH Keywords: relational database theory
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90121-4
OpenAlex ID: W2016035215
cites work: Hypergraphs with no special cycles
cites work: Characterizations of totally balanced matrices
cites work: Chordality properties on graphs and minimal conceptual connections in semantic data models
cites work: Distance-hereditary graphs
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q3941433
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: Characterizations of strongly chordal graphs
cites work: Hypergraphs without a large star
cites work: Q3328583
cites work: Tree queries
cites work: Syntactic Characterization of Tree Database Schemas
cites work: Parallel concepts in graph theory
cites work: Testing the universal instance assumption
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: On metric properties of certain clique graphs
cites work: A characterization of ptolemaic graphs
cites work: A Characterization of Certain Ptolemaic Graphs
cites work: Q3218167
cites work: A characterization of totally balanced hypergraphs
cites work: Q3880849
cites work: Connections in acyclic hypergraphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Steiner trees, connected domination and strongly chordal graphs
description: scientific article; zbMATH DE number 4083039