Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Algorithms Year : 2021

Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph

Abstract

The atom graph of a graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all possible atom trees of this graph. We provide two efficient algorithms for computing this atom graph, with a complexity in O(min(nωlogn,nm,n(n+m¯)) time, where n is the number of vertices of G, m is the number of its edges, m¯ is the number of edges of the complement of G, and ω, also denoted by α in the literature, is a real number, such that O(nω) is the best known time complexity for matrix multiplication, whose current value is 2,3728596. This time complexity is no more than the time complexity of computing the atoms in the general case. We extend our results to α-acyclic hypergraphs, which are hypergraphs having at least one join tree, a join tree of an hypergraph being defined by its hyperedges in the same way as an atom tree of a graph is defined by its atoms. We introduce the notion of union join graph, which is the union of all possible join trees; we apply our algorithms for atom graphs to efficiently compute union join graphs.
Fichier principal
Vignette du fichier
algorithms-14-00347-v2.pdf (516.42 Ko) Télécharger le fichier

Dates and versions

lirmm-03587020 , version 1 (24-02-2022)

Licence

Attribution

Identifiers

Cite

Anne Berry, Geneviève Simonet. Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph. Algorithms, 2021, 14 (12), pp.347-367. ⟨10.3390/a14120347⟩. ⟨lirmm-03587020⟩
64 View
43 Download

Altmetric

Share

Gmail Facebook X LinkedIn More