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

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

Alessandro D'Atri, Giorgio Ausiello

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

acyclicitybipartite graphsSteiner treerelational databaseschordality propertiesminimal connection among a set of objectssemantic data model

Mathematics Subject Classification ID

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

Related Items (17)

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 ⋮ An algorithm for determining minimal reduced-coverings of acyclic database schemes ⋮ On hypergraph acyclicity and graph chordality ⋮ Dually chordal graphs ⋮ On locally presented posets ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ On-line computation of minimal and maximal length paths ⋮ Problems with generalized Steiner problems ⋮ Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Coding Theory Motivated by Relational Databases ⋮ A fast algorithm for query optimization in universal-relation databases ⋮ On stable cutsets in graphs ⋮ Recognizing different types of beta-cycles in a database scheme

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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