On Digraph Width Measures in Parameterized Algorithmics

D 2009

On Digraph Width Measures in Parameterized Algorithmics

GANIAN, Robert; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Alexander LANGER; Joachim KNEIS et al.

Základní údaje

Originální název

On Digraph Width Measures in Parameterized Algorithmics

Název česky

O orientovaných šířkových parametrech v parametrizovaných algoritmech

Autoři

GANIAN, Robert; Petr HLINĚNÝ ; Jan OBDRŽÁLEK; Alexander LANGER; Joachim KNEIS a Peter ROSSMANITH

Vydání

5917. vyd. Berlin, IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, od s. 185-197, 13 s. 2009

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Dánsko

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

Conference, DOI

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/09:00065869

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-11268-3

ISSN

DOI

https://doi.org/10.1007/978-3-642-11269-0_15

UT WoS

000278758300015

Klíčová slova česky

digraph; DAG-width; bi-rank-width; parameterized complexity

Klíčová slova anglicky

digraph; DAG-width; bi-rank-width; parameterized complexity

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 30. 4. 2014 05:54, RNDr. Pavel Šmerk, Ph.D.

Anotace

ORIG CZ

V originále

In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAGwidth or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer-Ordyniak, Dankelmann-Gutin-Kim, or Lampis-Kaouri-Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAGdepth. On the positive side, we also note that taking Kanté's directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.

Česky

Rozebíráme obšírně důvody, proč orientované analogie klasických šířkových parametrů grafů nedávají uspokojivé algoritmické výsledky.

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

GC201/09/J021, projekt VaV

Název: Strukturální teorie grafů a parametrizovaná složitost

Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost

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

Citovat

GANIAN, Robert; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Alexander LANGER; Joachim KNEIS a Peter ROSSMANITH. On Digraph Width Measures in Parameterized Algorithmics. In IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science. 5917. vyd. Berlin: Springer Verlag, 2009, s. 185-197. ISBN 978-3-642-11268-3. Dostupné z: https://doi.org/10.1007/978-3-642-11269-0_15.

@inproceedings{863704,
   author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan and Langer, Alexander and Kneis, Joachim and Rossmanith, Peter},
   address = {Berlin},
   booktitle = {IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science},
   doi = {https://doi.org/10.1007/978-3-642-11269-0_15},
   edition = {5917},
   keywords = {digraph; DAG-width; bi-rank-width; parameterized complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-642-11268-3},
   pages = {185-197},
   publisher = {Springer Verlag},
   title = {On Digraph Width Measures in Parameterized Algorithmics},
   url = {http://dx.doi.org/10.1007/978-3-642-11269-0_15},
   year = {2009}
}

TY  - CONF
ID  - 863704
AU  - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan - Langer, Alexander - Kneis, Joachim - Rossmanith, Peter
PY  - 2009
TI  - On Digraph Width Measures in Parameterized Algorithmics
PB  - Springer Verlag
CY  - Berlin
SN  - 9783642112683
KW  - digraph
KW  - DAG-width
KW  - bi-rank-width
KW  - parameterized complexity
UR  - http://dx.doi.org/10.1007/978-3-642-11269-0_15
N2  - In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAGwidth or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer-Ordyniak, Dankelmann-Gutin-Kim, or Lampis-Kaouri-Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAGdepth. On the positive side, we also note that taking Kanté's directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.
ER  -

GANIAN, Robert; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Alexander LANGER; Joachim KNEIS a Peter ROSSMANITH. On Digraph Width Measures in Parameterized Algorithmics. In \textit{IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science}. 5917. vyd. Berlin: Springer Verlag, 2009, s.~185-197. ISBN~978-3-642-11268-3. Dostupné z: https://doi.org/10.1007/978-3-642-11269-0\_{}15.

Přehled o publikaci