Using Neighborhood Diversity to Solve Hard Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00057221" target="_blank" >RIV/00216224:14330/11:00057221 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Using Neighborhood Diversity to Solve Hard Problems

Popis výsledku v původním jazyce

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 asa 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 thatsimple parameterized algorithms exist for a few problems on graphs of bounded neighborhood diversity.

Název v anglickém jazyce

Using Neighborhood Diversity to Solve Hard Problems

Popis výsledku anglicky

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 asa 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 thatsimple parameterized algorithms exist for a few problems on graphs of bounded neighborhood diversity.

Druh

O - Ostatní výsledky

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů