Digraph measures: Kelly decompositions, games, and orderings

DOI10.1016/j.tcs.2008.02.038zbMath1152.91015OpenAlexW2090787331MaRDI QIDQ930893

Stephan Kreutzer, Paul Hunter

Publication date: 24 June 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:6dd728d5-d2f7-4911-9499-3e76990cff4b

zbMATH Keywords

directed graphsgraph decompositionscop and robber games

Mathematics Subject Classification ID

Games involving graphs (91A43)

Related Items

An algorithmic metatheorem for directed treewidth ⋮ Computing the zig-zag number of directed graphs ⋮ On the monotonicity of process number ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Directed width parameters on semicomplete digraphs ⋮ Jumping robbers in digraphs ⋮ DAG-width is PSPACE-complete ⋮ Parameterized Algorithms for Parity Games ⋮ Entanglement and the complexity of directed graphs ⋮ Chordal digraphs ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ Are there any good digraph width measures? ⋮ Directed elimination games ⋮ Twin-distance-hereditary digraphs ⋮ Directed NLC-width ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ The dag-width of directed graphs ⋮ Digraphs of bounded elimination width ⋮ Digraph width measures in parameterized algorithmics ⋮ Parity games on undirected graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ Approximation algorithms for digraph width parameters ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Forbidden directed minors and Kelly-width ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Recognizing digraphs of Kelly-width 2 ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Unnamed Item ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Unnamed Item ⋮ Are There Any Good Digraph Width Measures? ⋮ Directed width parameters and circumference of digraphs ⋮ DAG-Width and Circumference of Digraphs ⋮ Directed Path-Decompositions ⋮ On width measures and topological problems on semi-complete digraphs ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Digraphs of Bounded Width ⋮ Well-quasi-ordering hereditarily finite sets ⋮ Unnamed Item ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fugitive-search games on graphs and related parameters
• Graph searching, elimination trees, and a generalization of bandwidth
• Directed tree-width
• Automata, logics, and infinite games. A guide to current research
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• Directed path-width and monotonicity in digraph searching
• Triangulated graphs and the elimination process
• Rank-width and vertex-minors
• Directed tree-width examples
• The Role of Elimination Trees in Sparse Factorization
• DAG-width
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Elimination Structures for Unsymmetric Sparse $LU$ Factors
• Digraph Decompositions and Monotonicity in Digraph Searching
• On Exact Algorithms for Treewidth
• DAG-Width and Parity Games
• Algorithms – ESA 2005
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Digraph measures: Kelly decompositions, games, and orderings