W zależności od ilości danych do przetworzenia generowanie pliku może się wydłużyć.

Jeśli generowanie trwa zbyt długo można ograniczyć dane np. zmniejszając zakres lat.

Rozdział

Pobierz BibTeX

Tytuł

A heuristic approach to the treedepth decomposition problem for large graphs

Autorzy

[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik

Dyscyplina naukowa (Ustawa 2.0)

[2.3] Informatyka techniczna i telekomunikacja

Rok publikacji

2021

Typ rozdziału

rozdział w monografii naukowej / referat

Język publikacji

angielski

Słowa kluczowe
EN
  • treedepth decomposition
  • elimination tree
  • separator
Streszczenie

EN In this article, we describe algorithms and techniques used in the method ExTREEm for the treedepth decomposition problem. ExTREEm won the heuristic track of the 5th Parameterized Algorithms and Computational Experiments Challenge (PACE 2020). It searches for a minimum-height treedepth decomposition of a graph via computing graph separators. Among concepts that are incorporated into the approach, we can distinguish a new objective function for evaluating separators, preprocessing based on finding treedepth decompositions in cactus subgraphs and on identification of graphlets, five algorithms for finding separators, a separator minimization method for a refinement of found separators, and a refinement of an obtained treedepth decomposition by merging techniques of tree rotations. This approach enables us to quickly obtain low-depth decompositions of very large graphs.

Data udostępnienia online

20.09.2021

Strony (od-do)

169 - 181

DOI

10.1007/978-3-030-86838-3_13

URL

https://link.springer.com/chapter/10.1007/978-3-030-86838-3_13

Książka

Graph-Theoretic Concepts in Computer Science : 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers

Zaprezentowany na

47th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2021, 23-25.06.2021, Warszawa, Polska

Punktacja Ministerstwa / rozdział

20

Punktacja Ministerstwa / konferencja (CORE)

140

Ta strona używa plików Cookies, w celu zapamiętania uwierzytelnionej sesji użytkownika. Aby dowiedzieć się więcej przeczytaj o plikach Cookies i Polityce Prywatności.