Directed elimination games

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00094247" target="_blank" >RIV/00216224:14330/16:00094247 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.dam.2014.08.030" target="_blank" >http://dx.doi.org/10.1016/j.dam.2014.08.030</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2014.08.030" target="_blank" >10.1016/j.dam.2014.08.030</a>

Result language
angličtina
Original language name
Directed elimination games
Original language description
While tools from structural graph theory such as tree- or path-width have proved to be highly successful in coping with computational intractability on undirected graphs, corresponding width measures for directed graphs have not yet fulfilled their promise for broad algorithmic applications on directed graphs. One reason for this is that in most existing digraph width measures the class of acyclic digraphs has small width which immediately implies hardness of problems such as computing directed dominating sets. Fernau and Meister (2014) introduce the concept of elimination width and a corresponding graph searching game which overcomes this problem with acyclic digraphs. In their paper, the focus was on structural characterizations of classes of digraphs of bounded elimination width. In this paper we study elimination width from an algorithmic and graph searching perspective.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
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)