We propose an algorithm for minimal triangulation which, using simple and efficient strategy, subdivides the input graph in different, almost non-overlapping, subgraphs. Using the technique of matrix multiplication for saturating the minimal separators, we show that the partition of the graph can be computed in time O(nα) where nα is the time required by the binary matrix multiplication. After saturating the minimal separators, the same procedure is recursively applied on each subgraphs. We also present a variant of the algorithm in which the minimum degree criterion is used. In this way, we obtain an algorithm that uses minimum degree criterion and at the same time produces a minimal triangulation, thus shedding new light on the effectiveness of the minimum degree heuristics.

Mezzini, M. (2011). Fast minimal triangulation algorithm using minimum degree criterion. THEORETICAL COMPUTER SCIENCE, 412(29), 3775-3787 [10.1016/j.tcs.2011.04.022].

Fast minimal triangulation algorithm using minimum degree criterion

MEZZINI, MAURO
2011

Abstract

We propose an algorithm for minimal triangulation which, using simple and efficient strategy, subdivides the input graph in different, almost non-overlapping, subgraphs. Using the technique of matrix multiplication for saturating the minimal separators, we show that the partition of the graph can be computed in time O(nα) where nα is the time required by the binary matrix multiplication. After saturating the minimal separators, the same procedure is recursively applied on each subgraphs. We also present a variant of the algorithm in which the minimum degree criterion is used. In this way, we obtain an algorithm that uses minimum degree criterion and at the same time produces a minimal triangulation, thus shedding new light on the effectiveness of the minimum degree heuristics.
Mezzini, M. (2011). Fast minimal triangulation algorithm using minimum degree criterion. THEORETICAL COMPUTER SCIENCE, 412(29), 3775-3787 [10.1016/j.tcs.2011.04.022].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/122495
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact