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://dx.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Ý (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

• Originální 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"
• WWW: 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: 0302-9743
• Doi: http://dx.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

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.

Anotace č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