On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

DOI10.1007/978-3-540-92182-0_22zbMath1183.68312OpenAlexW1583293230MaRDI QIDQ3596720

Michael Lampis, Valia Mitsou, Georgia Kaouri

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_22

zbMATH Keywords

treewidthparameterized complexitydigraph decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items

Are there any good digraph width measures? ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ Online maximum directed cut ⋮ On complexity of minimum leaf out-branching problem ⋮ Are There Any Good Digraph Width Measures? ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Unnamed Item