Other formats:
BibTeX
LaTeX
RIS
@inproceedings{904649, author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan and Kneis, Joachim and Meister, Daniel and Sikdar, Somnath and Rossmanith, Peter}, address = {India}, booktitle = {Parameterized and exact computation, IPEC 2010}, doi = {http://dx.doi.org/10.1007/978-3-642-17493-3_14}, edition = {6478}, keywords = {directed graphs; width measures; monadic second order logic; directed graph minors}, howpublished = {tištěná verze "print"}, language = {eng}, location = {India}, isbn = {978-3-642-17492-6}, pages = {135-146}, publisher = {Lecture Notes in Computer Science, Springer-Verlag}, title = {Are there any good digraph width measures?}, url = {http://dx.doi.org/10.1007/978-3-642-17493-3_14}, year = {2010} }
TY - JOUR ID - 904649 AU - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan - Kneis, Joachim - Meister, Daniel - Sikdar, Somnath - Rossmanith, Peter PY - 2010 TI - Are there any good digraph width measures? PB - Lecture Notes in Computer Science, Springer-Verlag CY - India SN - 9783642174926 KW - directed graphs KW - width measures KW - monadic second order logic KW - directed graph minors UR - http://dx.doi.org/10.1007/978-3-642-17493-3_14 N2 - 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 ER -
GANIAN, Robert, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Joachim KNEIS, Daniel MEISTER, Somnath SIKDAR and Peter ROSSMANITH. Are there any good digraph width measures? In \textit{Parameterized and exact computation, IPEC 2010}. 6478th ed. India: Lecture Notes in Computer Science, Springer-Verlag, 2010, p.~135-146. ISBN~978-3-642-17492-6. Available from: https://dx.doi.org/10.1007/978-3-642-17493-3\_{}14.
|