Clique separator decomposition in less than nmReport as inadecuate

Clique separator decomposition in less than nm - Download this document for free, or read online. Document in PDF available to download.

1 LIMOS - Laboratoire d-Informatique, de Modélisation et d-optimisation des Systèmes

Abstract : We address the problem of computing the atoms of the decomposition by clique minimal separators of a graph G also called the maximal prime subgraphs when a minimal triangulation H of G is given as part of the input. We present a new algorithmic technique based on the clique tree of H. We introduce a new graph parameter, m0, which is the number of edges belonging to no minimal separator of H. We give an algorithm which runs in Onm0 time, which improves the current Onm time for this problem. Another version of our algorithm runs in Onn+t time, where t is the number of 2-pairs of H. We show that our technique computes the atoms in On2 time for several graph classes, including the graphs with bounded treewidth, which improves the current On3 time for dense graphs by a factor of n.

Mots-clés : clique separator decomposition minimal triangulation atom maximal prime subgraph chordal graph clique tree

Author: Anne Berry - Romain Pogorelcnik -



Related documents