An algorithmic metatheorem for directed treewidth

DOI10.1016/j.dam.2015.10.020zbMath1333.05139arXiv1410.0589OpenAlexW2963004311MaRDI QIDQ266806

Mateus de Oliveira Oliveira

Publication date: 7 April 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.0589

zbMATH Keywords

algorithmic metatheoremscombinatorial slice theorydirected treewidthmonadic second order logic of graphstree-zig-zag number

Mathematics Subject Classification ID

Related Items (4)

Computing the zig-zag number of directed graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Directed Path-Decompositions ⋮ Digraphs of Bounded Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The dag-width of directed graphs
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Graph minors. XX: Wagner's conjecture
• Digraph measures: Kelly decompositions, games, and orderings
• On complexity of minimum leaf out-branching problem
• Call routing and the ratcatcher
• Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs
• Directed tree-width
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• Entanglement and the complexity of directed graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Digraph width measures in parameterized algorithmics
• Directed path-width and monotonicity in digraph searching
• Heuristics for the maximum outerplanar subgraph problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs
• Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
• Are There Any Good Digraph Width Measures?
• Easy problems for tree-decomposable graphs
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• Mathematical Foundations of Computer Science 2005
• The Transitive Reduction of a Directed Graph
• Logic for Programming, Artificial Intelligence, and Reasoning
• Hasse Diagram Generators and Petri Nets
• Algorithms - ESA 2003

This page was built for publication: An algorithmic metatheorem for directed treewidth