On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

DOI10.1007/978-3-540-92182-0_22MaRDI QIDQ3596720zbMATH OpenOpenAlexFDO

Authors Michael Lampis, Georgia Kaouri, Valia Mitsou

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

digraph decompositionsparameterized complexitytreewidth

Mathematics Subject Classification ID

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

Recommendations

• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• Approximation algorithms for digraph width parameters
• Are there any good digraph width measures?

Cited in

(14)

• An iterative procedure for evaluating digraph competitions
• Digraph width measures in parameterized algorithmics
• Are there any good digraph width measures?
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• On digraph width measures in parameterized algorithmics
• Online maximum directed cut
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Approximation algorithms for digraph width parameters
• Directed nowhere dense classes of graphs
• Digraph decompositions and monotonicity in digraph searching
• A randomized rounding approach for DAG edge deletion
• Parameterized algorithms for directed modular width
• Are there any good digraph width measures?
• On complexity of minimum leaf out-branching problem

This page was built for publication: On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3596720)