Chordality properties on graphs and minimal conceptual connections in semantic data models

DOI10.1016/0022-0000(86)90018-8MaRDI QIDQ579964zbMATH OpenOpenAlexFDO

Authors Giorgio Ausiello, Alessandro D'Atri

Publication date 1986

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(86)90018-8

zbMATH Keywords

relational databasesbipartite graphsSteiner treeacyclicitychordality propertiesminimal connection among a set of objectssemantic data model

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Semantic acyclicity on graph databases
• Characterizations and algorithmic applications of chordal graph embeddings
• scientific article; zbMATH DE number 4198043
• Chordal graph models of contingency tables
• scientific article; zbMATH DE number 1670898
• scientific article; zbMATH DE number 1670897
• On the chordality of a graph
• scientific article; zbMATH DE number 1533810

Cites work

• scientific article; zbMATH DE number 3839362 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3890770 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Connections in acyclic hypergraphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• On the Desirability of Acyclic Database Schemes
• 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

Cited in

(17)

• Problems with generalized Steiner problems
• Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
• Distance Hereditary Graphs and the Interlace Polynomial
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Alternating cycle-free matchings
• Coding theory motivated by relational databases
• On hypergraph acyclicity and graph chordality
• A fast algorithm for query optimization in universal-relation databases
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• On-line computation of minimal and maximal length paths
• An algorithm for determining minimal reduced-coverings of acyclic database schemes
• Dually chordal graphs
• On locally presented posets
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• A distributed algorithm for determining minimal covers of acyclic database schemes
• Recognizing different types of beta-cycles in a database scheme
• On stable cutsets in graphs

This page was built for publication: Chordality properties on graphs and minimal conceptual connections in semantic data models

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