Are there any good digraph width measures?

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 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.

Basic information

• Original name: Are there any good digraph width measures?
• Authors: GANIAN, Robert (840 United States of America, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution), Joachim KNEIS (276 Germany), Daniel MEISTER (276 Germany), Somnath SIKDAR (356 India) and Peter ROSSMANITH (276 Germany).
• Edition: 6478. vyd. India, Parameterized and exact computation, IPEC 2010, p. 135-146, 12 pp. 2010.
• Publisher: Lecture Notes in Computer Science, Springer-Verlag

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: India
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• WWW: DOI
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/10:00065886
• Organization unit: Faculty of Informatics
• ISBN: 978-3-642-17492-6
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-642-17493-3_14
• UT WoS: 000286165700014
• Keywords in English: directed graphs; width measures; monadic second order logic; directed graph minors
• Tags: International impact, Reviewed

Abstract

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

Links

• GA201/08/0308, research and development project: Name: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Investor: Czech Science Foundation, Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity

• GC201/09/J021, research and development project: Name: Strukturální teorie grafů a parametrizovaná složitost

Investor: Czech Science Foundation, Structural graph theory and parameterized complexity

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

• MUNI/A/0914/2009, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)

Investor: Masaryk University, Category A

• MUNI/E/0059/2009, interní kód MU: Name: Parameterized Algorithms and Width measures on Graphs

Investor: Masaryk University, Category E - development project + specific research