Graph searching and a min-max theorem for tree-width
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 176249
- Connected Treewidth and Connected Graph Searching
- Tree-Width and Optimization in Bounded Degree Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 772777
- Nondeterministic graph searching: from pathwidth to treewidth
- Mathematical Foundations of Computer Science 2005
- Graph searching, elimination trees, and a generalization of bandwidth
- Graph-Theoretic Concepts in Computer Science
- On the maximum cardinality search lower bound for treewidth
Cited in
(only showing first 100 items - show all)- Graph searching with advice
- Affine systems of equations and counting infinitary logic
- Nondeterministic graph searching: from pathwidth to treewidth
- Submodular partition functions
- Quickly excluding a forest
- Excluding infinite minors
- A two-person game on graphs where each player tries to encircle his opponent's men
- The summation and bottleneck minimization for single-step searching on weighted graphs
- Fugitive-search games on graphs and related parameters
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- On the monotonicity of games generated by symmetric submodular functions.
- Localization game on geometric and planar graphs
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Visibility graphs, dismantlability, and the cops and robbers game
- A peeling algorithm for multiple testing on a random field
- A unified treatment of linked and lean tree-decompositions
- A branch-and-price-and-cut method for computing an optimal bramble
- Directed tree-width
- Entanglement and the complexity of directed graphs
- Locating a robber on a graph via distance queries
- Cops and Robber game with a fast robber on expander graphs and random graphs
- On tradeoffs between width- and fill-like graph parameters
- A new lower bound on graph gonality
- On the scramble number of graphs
- On the treewidth of Hanoi graphs
- One-visibility cops and robber on trees: optimal cop-win strategies
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- On objects dual to tree-cut decompositions
- Treewidth and gonality of glued grid graphs
- Treewidth is a lower bound on graph gonality
- On the gonality of Cartesian products of graphs
- Cooperative exploration and protection of a workspace assisted by information networks
- Tree-width and planar minors
- Pursuing a fast robber on a graph
- Characterization of graphs and digraphs with small process numbers
- Tangle and ultrafilter: game theoretical interpretation
- Treewidth of graphs with balanced separations
- Non-deterministic graph searching in trees
- Synthesizing structured reactive programs via deterministic tree automata
- A robber locating strategy for trees
- Tree sets
- Characterizing graphs of maximum matching width at most 2
- On digraph coloring problems and treewidth duality
- The theory of guaranteed search on graphs
- Digraph width measures in parameterized algorithmics
- On the complexity of planning for agent teams and its implications for single agent planning
- Hypertree width and related hypergraph invariants
- Lower bounds on the pathwidth of some grid-like graphs
- On tree width, bramble size, and expansion
- Canonical tree-decompositions of finite graphs. II. Essential parts
- Directed tree-width examples
- Complexity and monotonicity results for domination games
- Representations of infinite tree sets
- The mixed search game against an agile and visible fugitive is monotone
- On strict brambles
- DAG-width and circumference of digraphs
- Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
- Variations on cops and robbers
- Chasing a fast robber on planar graphs and random graphs
- Unifying duality theorems for width parameters in graphs and matroids (extended abstract)
- Parameters tied to treewidth
- Tangle and Maximal Ideal
- Contraction obstructions for connected graph searching
- On the monotonicity of process number
- Bounds on vertex colorings with restrictions on the union of color classes
- LIFO-search on digraphs: a searching game for cycle-rank
- Digraphs of bounded width
- Constructing Brambles
- A game of cops and robbers on graphs with periodic edge-connectivity
- Jumping robbers in digraphs
- Canonical tree-decompositions of a graph that display its k-blocks
- Graph Searching in a Crime Wave
- Monotonicity of Non-deterministic Graph Searching
- Hypertree-width and related hypergraph invariants
- On Cartesian Trees and Range Minimum Queries
- Tree-Width for First Order Formulae
- Tree projections: Game characterization and computational aspects
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- A Separator Theorem for Nonplanar Graphs
- scientific article; zbMATH DE number 176249 (Why is no real title available?)
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Nordhaus-Gaddum for treewidth
- Tree-width of hypergraphs and surface duality
- scientific article; zbMATH DE number 1104337 (Why is no real title available?)
- The dag-width of directed graphs
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- On the block number of graphs
- Criticality for multicommodity flows
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- The fast robber on interval and chordal graphs
- Approximation algorithms for digraph width parameters
- Capture bounds for visibility-based pursuit evasion
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Optimal parametric search on graphs of bounded tree-width
- Constant congestion brambles in directed graphs
- Properties of large 2-crossing-critical graphs
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Adapting the directed grid theorem into an FPT algorithm
This page was built for publication: Graph searching and a min-max theorem for tree-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1325271)
