An algorithmic metatheorem for directed treewidth

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00458530" target="_blank" >RIV/67985840:_____/16:00458530 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.dam.2015.10.020" target="_blank" >http://dx.doi.org/10.1016/j.dam.2015.10.020</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2015.10.020" target="_blank" >10.1016/j.dam.2015.10.020</a>

Jazyk výsledku

angličtina

Název v původním jazyce

An algorithmic metatheorem for directed treewidth

Popis výsledku v původním jazyce

The notion of directed treewidth was introduced by Johnson et al. (2001) as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem.

Název v anglickém jazyce

An algorithmic metatheorem for directed treewidth

Popis výsledku anglicky

The notion of directed treewidth was introduced by Johnson et al. (2001) as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

204

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

28

Strana od-do

49-76

Kód UT WoS článku

000374354300007

EID výsledku v databázi Scopus

2-s2.0-84992309958