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. s. 135-146. ISBN 978-3-642-17492-6. doi:10.1007/978-3-642-17493-3_14. 2010.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Are there any good digraph width measures?
Autoři GANIAN, Robert (840 Spojené státy, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Jan OBDRŽÁLEK (203 Česká republika, domácí), Joachim KNEIS (276 Německo), Daniel MEISTER (276 Německo), Somnath SIKDAR (356 Indie) a Peter ROSSMANITH (276 Německo).
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
Originální 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"
WWW DOI
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14330/10:00065886
Organizační jednotka Fakulta informatiky
ISBN 978-3-642-17492-6
ISSN 0302-9743
Doi http://dx.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
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 30. 4. 2014 04:22.
Anotace
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 VaVNá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 VaVNázev: Strukturální teorie grafů a parametrizovaná složitost
Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost
MSM0021622419, záměrNá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 MUNá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 MUNá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
VytisknoutZobrazeno: 28. 3. 2024 14:36