2013
Parameterized Algorithms for Modular-Width
GAJARSKÝ, Jakub, Michael LAMPIS a Sebastian ORDYNIAKZákladní údaje
Originální název
Parameterized Algorithms for Modular-Width
Autoři
GAJARSKÝ, Jakub (703 Slovensko, garant, domácí), Michael LAMPIS (300 Řecko) a Sebastian ORDYNIAK (276 Německo, domácí)
Vydání
Berlin Heidelberg, Parameterized and Exact Computation, od s. 163-176, 14 s. 2013
Nakladatel
Springer International Publishing
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/13:00066750
Organizační jednotka
Fakulta informatiky
ISBN
978-3-319-03897-1
ISSN
Klíčová slova anglicky
parameterized complexity; modular width; shrub depth; chromatic number; hamiltonian path
Změněno: 24. 4. 2014 19:24, RNDr. Pavel Šmerk, Ph.D.
Anotace
V originále
It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILP and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the “price of generality” paid by clique-width.
Návaznosti
EE2.3.30.0009, projekt VaV |
| ||
GAP202/11/0196, projekt VaV |
| ||
MUNI/A/0739/2012, interní kód MU |
| ||
MUNI/A/0760/2012, interní kód MU |
|