Computing Treewidth via Exact and Heuristic Lists of Minimal Separators

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We develop practically efficient algorithms for computing the treewidth (formula presented) of a graph G. The core of our approach is a new dynamic programming algorithm which, given a graph G, a positive integer k, and a set (formula presented) of minimal separators of G, decides if G has a tree-decomposition of width at most k of a certain canonical form that uses minimal separators only from in the sense that the intersection of every pair of adjacent bags belongs to. This algorithm is used to show a lower bound of (formula presented), setting to be the set of all minimal separators of cardinality at most k and to show an upper bound of k on (formula presented) to be some, hopefully rich, set of such minimal separators. Combining this algorithm with new algorithms for exact and heuristic listing of minimal separators, we obtain exact algorithms for treewidth which overwhelmingly outperform previously implemented algorithms.

Original languageEnglish
Title of host publicationAnalysis of Experimental Algorithms - Special Event,SEA² 2019, Revised Selected Papers
EditorsIlias Kotsireas, Panos Pardalos, Arsenis Tsokas, Konstantinos E. Parsopoulos, Dimitris Souravlias
PublisherSpringer
Pages219-236
Number of pages18
ISBN (Print)9783030340285
DOIs
Publication statusPublished - 1 Jan 2019
EventSpecial Event on Analysis of Experimental Algorithms, SEA² 2019 - Kalamata, Greece
Duration: 24 Jun 201929 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11544 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceSpecial Event on Analysis of Experimental Algorithms, SEA² 2019
CountryGreece
CityKalamata
Period24/06/1929/06/19

Fingerprint Dive into the research topics of 'Computing Treewidth via Exact and Heuristic Lists of Minimal Separators'. Together they form a unique fingerprint.

  • Cite this

    Tamaki, H. (2019). Computing Treewidth via Exact and Heuristic Lists of Minimal Separators. In I. Kotsireas, P. Pardalos, A. Tsokas, K. E. Parsopoulos, & D. Souravlias (Eds.), Analysis of Experimental Algorithms - Special Event,SEA² 2019, Revised Selected Papers (pp. 219-236). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11544 LNCS). Springer. https://doi.org/10.1007/978-3-030-34029-2_15