Digraph decompositions and monotonicity in digraph searching

DOI10.1016/J.TCS.2011.05.003MaRDI QIDQ638540zbMATH OpenOpenAlexFDO

Authors Stephan Kreutzer, Sebastian Ordyniak

Publication date 12 September 2011

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

Full work available at URL https://doi.org/10.1016/j.tcs.2011.05.003

zbMATH Keywords

monotonicityentanglementcops and robber gamesgraph searchingDAG-widthKelly-widthdirected path-widthdirected tree-width

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Recommendations

• Digraph Decompositions and Monotonicity in Digraph Searching
• Monotonicity in digraph search problems
• On the monotonicity of process number
• The dag-width of directed graphs
• Directed Searching Digraphs: Monotonicity and Complexity

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• An annotated bibliography on guaranteed graph searching
• Are there any good digraph width measures?
• DAG-Width and Parity Games
• DAG-width
• Digraph Decompositions and Monotonicity in Digraph Searching
• Digraph Strong Searching: Monotonicity and Complexity
• Digraph measures: Kelly decompositions, games, and orderings
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Fugitive-search games on graphs and related parameters
• Graph searching and a min-max theorem for tree-width
• Graph searching games
• Introducing directed tree width
• Logic for Programming, Artificial Intelligence, and Reasoning
• Mathematical Foundations of Computer Science 2005
• Monotonicity in graph searching
• Monotonicity of non-deterministic graph searching
• On digraph width measures in parameterized algorithmics
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• On the monotonicity of games generated by symmetric submodular functions.
• Recontamination does not help to search a graph
• Searching and sweeping graphs: a brief survey
• Searching for a Visible, Lazy Fugitive
• Sweeping graphs with large clique number

Cited in

(14)

• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• The dag-width of directed graphs
• What's next? Future directions in parameterized complexity
• Monotonicity of the cops and robber game for bounded depth treewidth
• On the monotonicity of process number
• Monotonicity of strong searching on digraphs
• Digraph Decompositions and Monotonicity in Digraph Searching
• Digraph Strong Searching: Monotonicity and Complexity
• The treewidth of proofs
• Adapting the directed grid theorem into an FPT algorithm
• Directed elimination games
• Digraph width measures in parameterized algorithmics
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Digraphs of bounded width

This page was built for publication: Digraph decompositions and monotonicity in digraph searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638540)