Clique-width: When Hard Does Not Mean Impossible

GANIAN, Robert, Petr HLINĚNÝ a Jan OBDRŽÁLEK. Clique-width: When Hard Does Not Mean Impossible. Online. In Thomas Schwentick and Christoph D{\"u}rr. 28th International Symposium on Theoretical Aspects of Computer Science STACS2011. 2011. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2011, s. 404-415. ISBN 978-3-939897-25-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.STACS.2011.404.

Základní údaje

Originální název

Clique-width: When Hard Does Not Mean Impossible

Název česky

Clique-width: když těžké není nemožné

Autoři

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

Vydání

2011. vyd. Dagstuhl, Germany, 28th International Symposium on Theoretical Aspects of Computer Science STACS2011, od s. 404-415, 12 s. 2011

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

---

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í

elektronická verze "online"

Odkazy

DOI STACS2011

Kód RIV

RIV/00216224:14330/11:00049978

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-25-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404

UT WoS

000392600500034

Klíčová slova anglicky

clique-width; parameterized algorithm; XP

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, there still exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf.\ also Minimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches.

Česky

Předkládáme nestandardní XP algoritmy pro problémy MinLOB a hranově disjunktní cesty na orientovaných grafech omezené clique-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ů
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