Are there any good digraph width measures?

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

Nalezeny alternativní kódy

RIV/00216224:14330/10:00065886

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Are there any good digraph width measures?

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Are there any good digraph width measures?

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2010

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 statě ve sborníku

Parameterized and exact computation, IPEC 2010

ISBN

978-3-642-17492-6

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Lecture Notes in Computer Science, Springer-Verlag

Místo vydání

India

Místo konání akce

Chennai, India

Datum konání akce

1. 1. 2010

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000000