DAG-width
From MaRDI portal
Publication:3581553
DOI10.1145/1109557.1109647zbMath1192.05065MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C20: Directed graphs (digraphs), tournaments
05C40: Connectivity
Related Items
Unnamed Item, Directed Path-Decompositions, Digraph Decompositions and Monotonicity in Digraph Searching, The Complexity of Nash Equilibria in Infinite Multiplayer Games, Unnamed Item, Jumping robbers in digraphs, The dag-width of directed graphs, On the algorithmic effectiveness of digraph decompositions and complexity measures, Approximation algorithms for digraph width parameters, Forbidden directed minors and Kelly-width, Digraph decompositions and monotonicity in digraph searching, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Directed width parameters and circumference of digraphs, Are there any good digraph width measures?, Monotonicity of non-deterministic graph searching, Digraph measures: Kelly decompositions, games, and orderings, An annotated bibliography on guaranteed graph searching, Digraph searching, directed vertex separation and directed pathwidth, On complexity of minimum leaf out-branching problem, Recognizing digraphs of Kelly-width 2, Entanglement and the complexity of directed graphs, How to compute digraph width measures on directed co-graphs, An extended tree-width notion for directed graphs related to the computation of permanents, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Complexity of node coverage games, Monotonicity of strong searching on digraphs, Digraphs of bounded elimination width, Are There Any Good Digraph Width Measures?, LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Digraphs of Bounded Width, Monotonicity of Non-deterministic Graph Searching, Characterization and Recognition of Digraphs of Bounded Kelly-width, Finite Automata, Digraph Connectivity, and Regular Expression Size, The Descriptive Complexity of Parity Games, On Digraph Width Measures in Parameterized Algorithmics
