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

DOI10.1016/0022-0000(86)90018-8zbMath0625.68076MaRDI QIDQ579964

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

acyclicity; bipartite graphs; Steiner tree; relational databases; chordality properties; minimal connection among a set of objects; semantic data model

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68P05: Data structures

68P20: Information storage and retrieval of data

Related Items

Distance Hereditary Graphs and the Interlace Polynomial, Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs, Recognizing different types of beta-cycles in a database scheme, On locally presented posets, On hypergraph acyclicity and graph chordality, On-line computation of minimal and maximal length paths, Problems with generalized Steiner problems, A fast algorithm for query optimization in universal-relation databases, Alternating cycle-free matchings, A parallel algorithm for computing Steiner trees in strongly chordal graphs, A distributed algorithm for determining minimal covers of acyclic database schemes, On stable cutsets in graphs, An algorithm for determining minimal reduced-coverings of acyclic database schemes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connections in acyclic hypergraphs
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational 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