DAG-width
From MaRDI portal
Publication:3581553
DOI10.1145/1109557.1109647zbMath1192.05065OpenAlexW4240256729MaRDI QIDQ3581553
Publication date: 16 August 2010
Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1109557.1109647
Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (36)
Digraph Decompositions and Monotonicity in Digraph Searching ⋮ Jumping robbers in digraphs ⋮ Entanglement and the complexity of directed graphs ⋮ Are there any good digraph width measures? ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ Characterization and Recognition of Digraphs of Bounded Kelly-width ⋮ Monotonicity of strong searching on digraphs ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ The dag-width of directed graphs ⋮ Digraphs of bounded elimination width ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ How to compute digraph width measures on directed co-graphs ⋮ The Descriptive Complexity of Parity Games ⋮ Monotonicity of non-deterministic graph searching ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ An annotated bibliography on guaranteed graph searching ⋮ Approximation algorithms for digraph width parameters ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Forbidden directed minors and Kelly-width ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ On complexity of minimum leaf out-branching problem ⋮ Recognizing digraphs of Kelly-width 2 ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Unnamed Item ⋮ Are There Any Good Digraph Width Measures? ⋮ Directed width parameters and circumference of digraphs ⋮ The Complexity of Nash Equilibria in Infinite Multiplayer Games ⋮ Directed Path-Decompositions ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Complexity of node coverage games
This page was built for publication: DAG-width
