Enumeration of Minimal Separators with Special Properties

Master Thesis (2022)
Author(s)

A.Y.F. Nardi Dei Da Filicaia Dotti (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

Mathijs de Weerdt – Mentor (TU Delft - Algorithmics)

E. Demirović – Mentor (TU Delft - Algorithmics)

Leo van Iersel – Mentor (TU Delft - Discrete Mathematics and Optimization)

Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright
© 2022 Andrea Nardi Dei Da Filicaia Dotti
More Info
expand_more
Publication Year
2022
Language
English
Copyright
© 2022 Andrea Nardi Dei Da Filicaia Dotti
Graduation Date
31-08-2022
Awarding Institution
Delft University of Technology
Programme
['Computer Science']
Faculty
Electrical Engineering, Mathematics and Computer Science
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

In this paper we give a historical and theoretical background to minimal triangulation and its relation to minimal separators.
We introduce a new type of minimal separators, the minimal meta separator, which its size is a lower bound for the treewidth problem, its fill-in is a lower bound for the minimum fill-in problem and can be used for the aid of enumeration of minimal separators.
Furthermore, we introduce the idea of transformation which are controlled graph modifications that predictably modify the minimal separators of such graph. Namely, we introduce the transformations of inclusion minimal clique decomposition, saturate minimal separator, edge addition and minimal meta separator decomposition. These transformations can aid the architecting of algorithms for the enumeration of minimal separators.
Finally, we then apply such methods on the problem of enumeration of minimal almost-clique separators and demonstrate faster runtimes compared to the current state of the art.

Files

Thesis..pdf
(pdf | 0.53 Mb)
License info not available