Directed path-width and monotonicity in digraph searching
From MaRDI portal
Publication:2502026
DOI10.1007/s00373-005-0627-yzbMath1138.05069OpenAlexW1976676758MaRDI QIDQ2502026
Publication date: 12 September 2006
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-005-0627-y
Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (44)
An algorithmic metatheorem for directed treewidth ⋮ Computing the zig-zag number of directed graphs ⋮ On the monotonicity of process number ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ Jumping robbers in digraphs ⋮ DAG-width is PSPACE-complete ⋮ A cops and robber game in multidimensional grids ⋮ Characterizations and directed path-width of sequence digraphs ⋮ Are there any good digraph width measures? ⋮ Directed elimination games ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ Monotonicity of strong searching on digraphs ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ The dag-width of directed graphs ⋮ Digraph width measures in parameterized algorithmics ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ How to compute digraph width measures on directed co-graphs ⋮ 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 ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Scanning Phylogenetic Networks Is NP-hard ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Forbidden directed minors and Kelly-width ⋮ Monotonicity in digraph search problems ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ On complexity of minimum leaf out-branching problem ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Directed Path-Decompositions ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ A Slice Theoretic Approach for Embedding Problems on Digraphs ⋮ Standard directed search strategies and their applications ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ Comparing linear width parameters for directed graphs ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
Cites Work
This page was built for publication: Directed path-width and monotonicity in digraph searching
