About: The DAG-width of directed graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: The DAG-width of directed graphs Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	The DAG-width of directed graphs The DAG-width of directed graphs (en)
skos:prefLabel	The DAG-width of directed graphs The DAG-width of directed graphs (en)
skos:notation	RIV/00216224:14330/12:00057892!RIV13-GA0-14330___
http://linked.open...avai/predkladatel	Fakulta informatiky
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GC201/09/J021)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Obdržálek, Jan
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	129528
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/12:00057892
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	tree-width; mu-calculus; model checking; parity games; decompositions; monotonicity; complexity; logic (en)
http://linked.open.../riv/klicoveSlovo	monotonicity complexity model checking decompositions mu-calculus parity games tree-width logic
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[E5C389959C8F]
http://linked.open...i/riv/nazevZdroje	Journal of Combinatorial Theory, Ser B
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	5 (xsd:int)
http://linked.open...vavai/riv/projekt	Structural graph theory and parameterized complexity
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	102
http://linked.open...iv/tvurceVysledku	Obdržálek, Jan Berwanger, Dietmar Dawar, Anuj Hunter, Paul Kreutzer, Stephan
http://linked.open...ain/vavai/riv/wos	000305492000005
issn	0095-8956
number of pages	24 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.jctb.2012.04.004
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	The DAG-width of directed graphs

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 41 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software