The DAG-width of directed graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00057892" target="_blank" >RIV/00216224:14330/12:00057892 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

The DAG-width of directed graphs

Popis výsledku v původním jazyce

Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm design. Tree-width can be characterised by a graph searching game where a number of cops attempt to capture a robber. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure, called DAG-width, that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). We also provide an associated decomposition and show how it is useful for developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other connectivity measures such as directed tree-width and path-width.

Název v anglickém jazyce

The DAG-width of directed graphs

Popis výsledku anglicky

Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm design. Tree-width can be characterised by a graph searching game where a number of cops attempt to capture a robber. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure, called DAG-width, that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). We also provide an associated decomposition and show how it is useful for developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other connectivity measures such as directed tree-width and path-width.

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GC201%2F09%2FJ021" target="_blank" >GC201/09/J021: Strukturální teorie grafů a parametrizovaná složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

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

Journal of Combinatorial Theory, Ser B

ISSN

0095-8956

e-ISSN

—

Svazek periodika

102

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

24

Strana od-do

900-923

Kód UT WoS článku

000305492000005

EID výsledku v databázi Scopus

—