Are there any good digraph width measures?

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00045216" target="_blank" >RIV/00216224:14330/10:00045216 - isvavai.cz</a>

Alternative codes found

RIV/00216224:14330/10:00065886

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Are there any good digraph width measures?

Original language description

Several different measures for digraph width have appeared in the last few years. However, none of them shares all the ``nice'' properties of treewidth: First, being algorithmically useful - say, admitting polynomial-time algorithms for all MSO1-definable problems on digraphs of bounded width. And, second, having nice structural properties such as being monotone under taking subdigraphs and some form of arc contractions. Our main result then is that any reasonable algorithmically useful and structurallynice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach<br>O - Projekt operacniho programu

Publication year

2010

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Parameterized and exact computation, IPEC 2010

ISBN

978-3-642-17492-6

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

—

Publisher name

Lecture Notes in Computer Science, Springer-Verlag

Place of publication

India

Event location

Chennai, India

Event date

Jan 1, 2010

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000000