Entanglement and the complexity of directed graphs
type: Item
instance of: scholarly article
title: Entanglement and the complexity of directed graphs
zbMATH Open document ID: 1256.05086
author: Dietmar Berwanger
author: Erich Grädel
author: Łukasz Kaiser
author: Roman Rabinovich
published in: Theoretical Computer Science
publication date: 2013-01-07T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A24
zbMATH DE Number: 6122452
zbMATH Keywords: structural graph theory
zbMATH Keywords: graph searching games
zbMATH Keywords: parity games
zbMATH Keywords: digraph algorithms
zbMATH Keywords: treewidth
zbMATH Keywords: DAG-width
zbMATH Keywords: Kelly-width
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.07.010
OpenAlex ID: W1977644778
cites work: Q4039803
cites work: Undirected Graphs of Entanglement 2
cites work: DAG-Width and Parity Games
cites work: The dag-width of directed graphs
cites work: Logic for Programming, Artificial Intelligence, and Reasoning
cites work: Q4411834
cites work: The variable hierarchy of the \(\mu\)-calculus is strict
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Alternation
cites work: The Descriptive Complexity of Parity Games
cites work: Transition graphs and the star-height of regular events
cites work: Directed Graphs of Entanglement Two
cites work: Q2934648
cites work: Digraph measures: Kelly decompositions, games, and orderings
cites work: Directed tree-width
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q4501540
cites work: Results on the propositional \(\mu\)-calculus
cites work: Digraph Decompositions and Monotonicity in Digraph Searching
cites work: Computer Aided Verification
cites work: DAG-width
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. III. Planar tree-width
cites work: Graph searching and a min-max theorem for tree-width
cites work: Bisimulation, modal logic and model checking games
cites work: Infinite games on finitely coloured graphs with applications to automata on infinite trees
DOI: 10.1016/J.TCS.2012.07.010
description: scientific article; zbMATH DE number 6122452