Attributes | Values |
---|
rdf:type
| |
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 structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph
- 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 structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph (en)
|
Title
| - Are there any good digraph width measures?
- Are there any good digraph width measures? (en)
|
skos:prefLabel
| - Are there any good digraph width measures?
- Are there any good digraph width measures? (en)
|
skos:notation
| - RIV/00216224:14330/10:00065886!RIV14-MSM-14330___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - O, P(GA201/08/0308), P(GC201/09/J021), S, Z(MSM0021622419)
|
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216224:14330/10:00065886
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - directed graphs; width measures; monadic second order logic; directed graph minors (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| - Parameterized and exact computation, IPEC 2010
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| - Ganian, Robert
- Hliněný, Petr
- Obdržálek, Jan
- Rossmanith, Peter
- Sikdar, Somnath
- Kneis, Joachim
- Meister, Daniel
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open...ain/vavai/riv/wos
| |
http://linked.open.../riv/zahajeniAkce
| |
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |
http://bibframe.org/vocab/doi
| - 10.1007/978-3-642-17493-3_14
|
http://purl.org/ne...btex#hasPublisher
| - Lecture Notes in Computer Science, Springer-Verlag
|
https://schema.org/isbn
| |
http://localhost/t...ganizacniJednotka
| |