Graph searching and a min-max theorem for tree-width
From MaRDI portal
Publication:1325271
DOI10.1006/jctb.1993.1027zbMath0795.05110OpenAlexW2011911122WikidataQ29013944 ScholiaQ29013944MaRDI QIDQ1325271
Publication date: 30 June 1994
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1993.1027
Trees (05C05) Games involving graphs (91A43) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Complexity and monotonicity results for domination games ⋮ Variations on cops and robbers ⋮ Cops and robber on butterflies and solid grids ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Localization game on geometric and planar graphs ⋮ Contraction obstructions for connected graph searching ⋮ On the monotonicity of process number ⋮ Directed tree-width examples ⋮ Jumping robbers in digraphs ⋮ Canonical tree-decompositions of a graph that display its \(k\)-blocks ⋮ On objects dual to tree-cut decompositions ⋮ Representations of infinite tree sets ⋮ Parameterized pursuit-evasion games ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ A robber locating strategy for trees ⋮ Systematic and deterministic graph minor embedding for Cartesian products of graphs ⋮ Treewidth and gonality of glued grid graphs ⋮ Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract) ⋮ Tree sets ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ 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 ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Fugitive-search games on graphs and related parameters ⋮ Are there any good digraph width measures? ⋮ Graph minors. XXII. Irrelevant vertices in linkage problems ⋮ Nordhaus-Gaddum for treewidth ⋮ On low tree-depth decompositions ⋮ On the treewidth of toroidal grids ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ Tree-width of hypergraphs and surface duality ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ A peeling algorithm for multiple testing on a random field ⋮ On digraph coloring problems and treewidth duality ⋮ On strict brambles ⋮ Treewidth is a lower bound on graph gonality ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ The dag-width of directed graphs ⋮ The theory of guaranteed search on graphs ⋮ Parameters Tied to Treewidth ⋮ Digraph width measures in parameterized algorithmics ⋮ Tangle and Maximal Ideal ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ On the complexity of planning for agent teams and its implications for single agent planning ⋮ Treewidth lower bounds with brambles ⋮ On the gonality of Cartesian products of graphs ⋮ Criticality for multicommodity flows ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Monotonicity of non-deterministic graph searching ⋮ An annotated bibliography on guaranteed graph searching ⋮ The fast robber on interval and chordal graphs ⋮ Approximation algorithms for digraph width parameters ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Capture bounds for visibility-based pursuit evasion ⋮ Quickly excluding a forest ⋮ Hypertree width and related hypergraph invariants ⋮ The pebbling threshold of the square of cliques ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Excluding infinite minors ⋮ A unified treatment of linked and lean tree-decompositions ⋮ \(K_{6}\) minors in large 6-connected graphs ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Cooperative exploration and protection of a workspace assisted by information networks ⋮ Lower bounds on the pathwidth of some grid-like graphs ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Connected graph searching in chordal graphs ⋮ Tree-width and planar minors ⋮ Pursuing a fast robber on a graph ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ CSP duality and trees of bounded pathwidth ⋮ Characterization of graphs and digraphs with small process numbers ⋮ Maximum vertex occupation time and inert fugitive: Recontamination does help ⋮ Connected tree-width ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Monotony properties of connected visible graph searching ⋮ On tree width, bramble size, and expansion ⋮ Graph searching with advice ⋮ Lower bounds for treewidth of product graphs ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ DAG-Width and Circumference of Digraphs ⋮ Affine systems of equations and counting infinitary logic ⋮ Tangle and ultrafilter: game theoretical interpretation ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ Treewidth of graphs with balanced separations ⋮ A new lower bound on graph gonality ⋮ On the scramble number of graphs ⋮ A two-person game on graphs where each player tries to encircle his opponent's men ⋮ On the treewidth of Hanoi graphs ⋮ One-visibility cops and robber on trees: optimal cop-win strategies ⋮ Submodular partition functions ⋮ Directed tree-width ⋮ Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles ⋮ Non-deterministic graph searching in trees ⋮ Synthesizing structured reactive programs via deterministic tree automata ⋮ Canonical tree-decompositions of finite graphs. II. Essential parts ⋮ Refining a Tree-Decomposition which Distinguishes Tangles ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Bounding the search number of graph products ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ Constructing Brambles ⋮ Constant Congestion Brambles in Directed Graphs ⋮ CFI Construction and Balanced Graphs ⋮ Treewidth of Cartesian Products of Highly Connected Graphs ⋮ Integer programming models and algorithms for the graph decontamination problem with mobile agents ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Constant Congestion Brambles ⋮ Combing a Linkage in an Annulus ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Connected search for a lazy robber ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ Graph Searching in a Crime Wave ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ On the Block Number of Graphs ⋮ A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity ⋮ Cops and robber on some families of oriented graphs ⋮ A Separator Theorem for Nonplanar Graphs ⋮ Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph ⋮ Fugitive-search games on graphs and related parameters ⋮ Bounding Connected Tree-Width ⋮ Unnamed Item ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Undirected Graphs of Entanglement 2 ⋮ Variations of cops and robbers game on grids ⋮ Directed Path-Decompositions ⋮ Bounds on vertex colorings with restrictions on the union of color classes ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ Tree-Width for First Order Formulae ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Searching for a Visible, Lazy Fugitive ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ Digraphs of Bounded Width ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Treewidth of the Line Graph of a Complete Graph ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Unnamed Item ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
