Clique-width: When Hard Does Not Mean Impossible

D 2011

Clique-width: When Hard Does Not Mean Impossible

GANIAN, Robert, Petr HLINĚNÝ and Jan OBDRŽÁLEK

Basic information

Original name

Clique-width: When Hard Does Not Mean Impossible

Name in Czech

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

Authors

GANIAN, Robert (840 United States of America, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution)

Edition

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

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

DOI STACS2011

RIV identification code

RIV/00216224:14330/11:00049978

Organization unit

Faculty of Informatics

ISBN

978-3-939897-25-5

ISSN

DOI

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

UT WoS

000392600500034

Keywords in English

clique-width; parameterized algorithm; XP

Abstract

ORIG CZ

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.

In Czech

Předkládáme nestandardní XP algoritmy pro problémy MinLOB a hranově disjunktní cesty na orientovaných grafech omezené clique-width.

Links

GAP202/11/0196, research and development project

Name: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů

Investor: Czech Science Foundation, Well-structured combinatorial classes, width parameters, and design of efficient algorithms

MUNI/A/0057/2011, interní kód MU

Name: Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKONF)

Investor: Masaryk University, Category A

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

1M0545, research and development project

Name: Institut Teoretické Informatiky

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

Citovat

GANIAN, Robert, Petr HLINĚNÝ and 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. 2011th ed. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2011, p. 404-415. ISBN 978-3-939897-25-5. Available from: https://dx.doi.org/10.4230/LIPIcs.STACS.2011.404.

@inproceedings{950101,
   author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan},
   address = {Dagstuhl, Germany},
   booktitle = {28th International Symposium on Theoretical Aspects of Computer Science STACS2011},
   doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404},
   edition = {2011},
   editor = {Thomas Schwentick and Christoph D{\"u}rr},
   keywords = {clique-width; parameterized algorithm; XP},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-939897-25-5},
   pages = {404-415},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS},
   title = {Clique-width: When Hard Does Not Mean Impossible},
   url = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404},
   year = {2011}
}

TY  - JOUR
ID  - 950101
AU  - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan
PY  - 2011
TI  - Clique-width: When Hard Does Not Mean Impossible
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
CY  - Dagstuhl, Germany
SN  - 9783939897255
KW  - clique-width
KW  - parameterized algorithm
KW  - XP
UR  - http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404
L2  - http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404
N2  - 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.
ER  -

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

Detailed Information on Publication Record