About: Digraph width measures in parameterized algorithmics

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

About: Digraph width measures in parameterized algorithmics Goto Sponge Distinct 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	In contrast to undirected width measures such as tree-width, which have provided many important algorithmic applications, analogous measures for digraphs such as directed tree-width or DAG-width do not seem so successful. Several recent papers have given some evidence on the negative side. We confirm and consolidate this overall picture by thoroughly and exhaustively studying the complexity of a range of directed problems with respect to various parameters, and by showing that they often remain NP-hard even on graph classes that are restricted very beyond having small DAG-width. On the positive side, it turns out that clique-width (of digraphs) performs much better on virtually all considered problems, from the parameterized complexity point of view. In contrast to undirected width measures such as tree-width, which have provided many important algorithmic applications, analogous measures for digraphs such as directed tree-width or DAG-width do not seem so successful. Several recent papers have given some evidence on the negative side. We confirm and consolidate this overall picture by thoroughly and exhaustively studying the complexity of a range of directed problems with respect to various parameters, and by showing that they often remain NP-hard even on graph classes that are restricted very beyond having small DAG-width. On the positive side, it turns out that clique-width (of digraphs) performs much better on virtually all considered problems, from the parameterized complexity point of view. (en)
Title	Digraph width measures in parameterized algorithmics Digraph width measures in parameterized algorithmics (en)
skos:prefLabel	Digraph width measures in parameterized algorithmics Digraph width measures in parameterized algorithmics (en)
skos:notation	RIV/00216224:14330/14:00073690!RIV15-GA0-14330___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GBP202/12/G061), P(GC201/09/J021)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Obdržálek, Jan Ganian, Robert Hliněný, Petr
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	11556
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/14:00073690
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Digraph; Parameterized complexity; Tree-width; DAG-width; DAG-depth; Clique-width (en)
http://linked.open.../riv/klicoveSlovo	Clique-width DAG-width Digraph Tree-width Parameterized complexity DAG-depth
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[783BEADA1B6A]
http://linked.open...i/riv/nazevZdroje	Discrete Applied Mathematics
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	6 (xsd:int)
http://linked.open...vavai/riv/projekt	Center of excellence - Institute for theoretical computer science (CE-ITI) Structural graph theory and parameterized complexity
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	168
http://linked.open...iv/tvurceVysledku	Ganian, Robert Hliněný, Petr Obdržálek, Jan Rossmanith, Peter Langer, Alexander Kneis, Joachim
http://linked.open...ain/vavai/riv/wos	000334485900011
issn	0166-218X
number of pages	20 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.dam.2013.10.038
http://localhost/t...ganizacniJednotka	14330

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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software