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 Accéder directement au contenu
Article Dans Une Revue Algorithms Année : 2021

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

Résumé

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 et versions

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

Licence

Paternité

Identifiants

Citer

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⟩
62 Consultations
42 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More