Clique separator decomposition in less than nmReportar como inadecuado

Clique separator decomposition in less than nm - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Anne Berry - Romain Pogorelcnik -



Documentos relacionados