Using Neighborhood Diversity to Solve Hard Problems

GANIAN, Robert. Using Neighborhood Diversity to Solve Hard Problems. 2011.

Základní údaje

Originální název

Using Neighborhood Diversity to Solve Hard Problems

Autoři

GANIAN, Robert (840 Spojené státy, garant, domácí)

Vydání

2011

---

Další údaje

Jazyk

angličtina

Typ výsledku

Prezentace na konferencích

Obor

10000 1. Natural Sciences

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Kód RIV

RIV/00216224:14330/11:00057221

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Neighborhood Diversity; Parameterized Complexity; FPT algorithms

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Parameterized algorithms are a very useful tool for dealing with NP-hard problems on graphs. Yet, to properly utilize parameterized algorithms it is necessary to choose the right parameter based on the type of problem and properties of the target graph class. Tree-width is an example of a very successful graph parameter, however it cannot be used on dense graph classes and there also exist problems which are hard even on graphs of bounded tree-width. Such problems can be tackled by using vertex cover as a parameter, however this places severe restrictions on admissible graph classes. Michael Lampis has recently introduced neighborhood diversity, a new graph parameter which generalizes vertex cover to dense graphs. Among other results, he has shown that simple parameterized algorithms exist for a few problems on graphs of bounded neighborhood diversity. Our article further studies this area and provides new algorithms parameterized by neighborhood diversity for the p-Vertex-Disjoint Paths, Graph Motif and Precoloring Extension problems -- the latter two being hard even on graphs of bounded tree-width.

---

Návaznosti

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ů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
MUNI/A/0057/2011, interní kód MU	Název: Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKONF) Investor: Masarykova univerzita, Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky