Directed elimination games

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Directed elimination games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Directed elimination games

Popis výsledku anglicky

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.

Druh

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

CEP obor

IN - Informatika

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

199

Číslo periodika v rámci svazku

C

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

187-198

Kód UT WoS článku

000368045700014

EID výsledku v databázi Scopus

—