D 2013

Parameterized Algorithms for Modular-Width

GAJARSKÝ, Jakub, Michael LAMPIS a Sebastian ORDYNIAK

Zá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

Štítky

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
Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
GAP202/11/0196, projekt VaV
Název: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Investor: Grantová agentura ČR, Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
MUNI/A/0739/2012, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0760/2012, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty