Computing the atom graph of a graph and the union join graph of a hypergraph

Autor: Anne Berry, Geneviève Simonet
Přispěvatelé: Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2016
Předmět:
FOS: Computer and information sciences
Hypergraph
Discrete Mathematics (cs.DM)
Industrial engineering. Management engineering
MathematicsofComputing_GENERAL
clique graph
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
T55.4-60.8
Clique (graph theory)
Clique graph
Computer Science::Digital Libraries
α-acyclic hypergraph
Theoretical Computer Science
clique separator decomposition
atom tree
atom graph
clique tree
Combinatorics
Computer Science::Discrete Mathematics
Computer Science - Data Structures and Algorithms
Physics::Atomic and Molecular Clusters
Data Structures and Algorithms (cs.DS)
Physics::Atomic Physics
Time complexity
Mathematics
Condensed Matter::Quantum Gases
Numerical Analysis
QA75.5-76.95
Tree (graph theory)
Matrix multiplication
Complement (complexity)
Computational Mathematics
Computational Theory and Mathematics
Electronic computers. Computer science
Computer Science::Programming Languages
Join (sigma algebra)
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Algorithms, Vol 14, Iss 347, p 347 (2021)
Algorithms; Volume 14; Issue 12; Pages: 347
Algorithms
Algorithms, 2021, 14 (12), pp.347-367. ⟨10.3390/a14120347⟩
ISSN: 1999-4893
DOI: 10.48550/arxiv.1607.02911
Popis: The atom graph of a graph is the 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^\alpha \log n, nm, n(n+\overline{m}))$ time, which is no more than the complexity of computing the atoms in the general case. %\par We extend our results to $\alpha$-acyclic hypergraphs. 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. Keywords: clique separator decomposition, atom tree, atom graph, clique tree, clique graph, $\alpha$-acyclic hypergraph.
Comment: Submitted in Algorithms on July 11, 2016
Databáze: OpenAIRE
Externí odkaz: