Better Polynomial Algorithms on Graphs of Bounded Rank-width.

GANIAN, Robert a Petr HLINĚNÝ. Better Polynomial Algorithms on Graphs of Bounded Rank-width. In IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874. 5874. vyd. Berlin: Springer, 2009, s. 266-277. ISBN 978-3-642-10216-5. Dostupné z: https://doi.org/10.1007/978-3-642-10217-2.

Základní údaje

Originální název

Better Polynomial Algorithms on Graphs of Bounded Rank-width.

Název česky

Lepší polynomiální algoritmy na grafech omezené rank-width

Autoři

GANIAN, Robert (840 Spojené státy, domácí) a Petr HLINĚNÝ ORCID (203 Česká republika, garant, domácí)

Vydání

5874. vyd. Berlin, IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874, od s. 266-277, 12 s. 2009

Nakladatel

Springer

---

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"

Odkazy

DOI

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/09:00065861

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-10216-5

ISSN

DOI

https://doi.org/10.1007/978-3-642-10217-2

UT WoS

000280084100026

Klíčová slova anglicky

rank-width; parameterized algorithms; graphs

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kante, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems.

Česky

Ačkoliv existuje mnoho polynomiálních algoritmů pro NP-těžké problémy na grafech omezené clique-width, o podobných algoritmech využívajících rank-width je toho známo velmi málo. Článek se zaměřuje na vývoj efektivních a formálně "čistých" algoritmů na grafech omezené rank-width.

---

Návaznosti

GA201/08/0308, projekt VaV	Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
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/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
MUNI/E/0059/2009, interní kód MU	Název: Parameterized Algorithms and Width measures on Graphs Investor: Masarykova univerzita, Parameterized Algorithms and Width measures on Graphs, Kat. E - Podpora výzkumné činnosti studentů v oborech lékařství, zdravotnictví, přírodovědy a informatiky - rozvojový projekt + specifický výzkum
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky