Better Polynomial Algorithms on Graphs of Bounded Rank-width.

GANIAN, Robert and 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. 5874th ed. Berlin: Springer, 2009, p. 266-277. ISBN 978-3-642-10216-5. Available from: https://dx.doi.org/10.1007/978-3-642-10217-2.

Basic information

• Original name: Better Polynomial Algorithms on Graphs of Bounded Rank-width.
• Name in Czech: Lepší polynomiální algoritmy na grafech omezené rank-width
• Authors: GANIAN, Robert (840 United States of America, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution).
• Edition: 5874. vyd. Berlin, IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874, p. 266-277, 12 pp. 2009.
• Publisher: Springer

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• WWW: DOI
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/09:00065861
• Organization unit: Faculty of Informatics
• ISBN: 978-3-642-10216-5
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-642-10217-2
• UT WoS: 000280084100026
• Keywords in English: rank-width; parameterized algorithms; graphs
• Tags: International impact, Reviewed

Abstract

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.

Abstract (in Czech)

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.

Links

• GA201/08/0308, research and development project: Name: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Investor: Czech Science Foundation, Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

• MUNI/A/0914/2009, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)

Investor: Masaryk University, Category A

• MUNI/E/0059/2009, interní kód MU: Name: Parameterized Algorithms and Width measures on Graphs

Investor: Masaryk University, Category E - development project + specific research

• 1M0545, research and development project: Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science