An algorithmic metatheorem for directed treewidth

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
An algorithmic metatheorem for directed treewidth
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)