Are there any good digraph width measures?

GANIAN, Robert; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Joachim KNEIS; Daniel MEISTER; Somnath SIKDAR a Peter ROSSMANITH. Are there any good digraph width measures? In Parameterized and exact computation, IPEC 2010. 6478. vyd. India: Lecture Notes in Computer Science, Springer-Verlag, 2010, s. 135-146. ISBN 978-3-642-17492-6. Dostupné z: https://doi.org/10.1007/978-3-642-17493-3_14.

Základní údaje

Originální název

Are there any good digraph width measures?

Autoři

GANIAN, Robert; Petr HLINĚNÝ ORCID; Jan OBDRŽÁLEK; Joachim KNEIS; Daniel MEISTER; Somnath SIKDAR a Peter ROSSMANITH

Vydání

6478. vyd. India, Parameterized and exact computation, IPEC 2010, od s. 135-146, 12 s. 2010

Nakladatel

Lecture Notes in Computer Science, Springer-Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Indie

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

DOI

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/10:00065886

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-17492-6

ISSN

DOI

https://doi.org/10.1007/978-3-642-17493-3_14

UT WoS

000286165700014

Klíčová slova anglicky

directed graphs; width measures; monadic second order logic; directed graph minors

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Several different measures for digraph width have appeared in the last few years. However, none of them shares all the ``nice'' properties of treewidth: First, being algorithmically useful - say, admitting polynomial-time algorithms for all MSO1-definable problems on digraphs of bounded width. And, second, having nice structural properties such as being monotone under taking subdigraphs and some form of arc contractions. Our main result then is that any reasonable algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph

---

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