Graph searching and a min-max theorem for tree-width
From MaRDI portal
Publication:1325271
DOI10.1006/JCTB.1993.1027zbMATH Open0795.05110OpenAlexW2011911122WikidataQ29013944 ScholiaQ29013944MaRDI QIDQ1325271FDOQ1325271
Authors: Robin Thomas, Paul Seymour 
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
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
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Games involving graphs (91A43)
Cited In (only showing first 100 items - show all)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Canonical tree-decompositions of finite graphs. II. Essential parts
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Non-deterministic graph searching in trees
- Title not available (Why is that?)
- On the gonality of Cartesian products of graphs
- Complexity and monotonicity results for domination games
- The pebbling threshold of the square of cliques
- Pursuing a fast robber on a graph
- The dag-width of directed graphs
- Nordhaus-Gaddum for treewidth
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Connected graph searching in chordal graphs
- Localization game on geometric and planar graphs
- Graphs without large apples and the maximum weight independent set problem
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Tree-width of hypergraphs and surface duality
- Bounding connected tree-width
- Mathematical Foundations of Computer Science 2005
- Uniform Constraint Satisfaction Problems and Database Theory
- An annotated bibliography on guaranteed graph searching
- Graph searching with advice
- Searching for a Visible, Lazy Fugitive
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Bounds on vertex colorings with restrictions on the union of color classes
- Treewidth lower bounds with brambles
- Polynomial treewidth forces a large grid-like-minor
- On the maximum cardinality search lower bound for treewidth
- A robber locating strategy for trees
- Contraction obstructions for connected graph searching
- On the monotonicity of process number
- Digraph Decompositions and Monotonicity in Digraph Searching
- \(K_{6}\) minors in large 6-connected graphs
- Directed tree-width
- Entanglement and the complexity of directed graphs
- Parameterized pursuit-evasion games
- Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
- Quickly excluding a forest
- Monotonicity of non-deterministic graph searching
- LIFO-search on digraphs: a searching game for cycle-rank
- Digraph searching, directed vertex separation and directed pathwidth
- Variations of cops and robbers game on grids
- Monotony properties of connected visible graph searching
- Undirected Graphs of Entanglement 2
- Cops and robber on butterflies and solid grids
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Fugitive-search games on graphs and related parameters
- Digraph width measures in parameterized algorithmics
- On the monotonicity of games generated by symmetric submodular functions.
- Hypertree-width and related hypergraph invariants
- Lower bounds on the pathwidth of some grid-like graphs
- On tree width, bramble size, and expansion
- Criticality for multicommodity flows
- Approximation algorithms for digraph width parameters
- The fast robber on interval and chordal graphs
- Chasing a fast robber on planar graphs and random graphs
- Hypertree width and related hypergraph invariants
- Tree-width and planar minors
- Jumping robbers in digraphs
- Canonical tree-decompositions of a graph that display its \(k\)-blocks
- Variations on cops and robbers
- Capture bounds for visibility-based pursuit evasion
- Digraph decompositions and monotonicity in digraph searching
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Characterization of graphs and digraphs with small process numbers
- On Cartesian Trees and Range Minimum Queries
- Locating a robber on a graph via distance queries
- Affine systems of equations and counting infinitary logic
- Nondeterministic graph searching: from pathwidth to treewidth
- Excluding infinite minors
- Directed tree-width examples
- CSP duality and trees of bounded pathwidth
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- A Separator Theorem for Nonplanar Graphs
- Representations of infinite tree sets
- Cops and Robber game with a fast robber on expander graphs and random graphs
- On digraph coloring problems and treewidth duality
- Title not available (Why is that?)
- Treewidth of graphs with balanced separations
- Title not available (Why is that?)
- Constructing tree decompositions of graphs with bounded gonality
- Tangle and Maximal Ideal
- Fugitive-search games on graphs and related parameters
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Directed path-decompositions
- Are there any good digraph width measures?
- A cop and robber game on edge-periodic temporal graphs
- DAG-width and circumference of digraphs
- Tree sets
- Submodular partition functions
- Tree-Width for First Order Formulae
- On tradeoffs between width- and fill-like graph parameters
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- The cordiality game and the game cordiality number
- A unified treatment of linked and lean tree-decompositions
- Maximum vertex occupation time and inert fugitive: Recontamination does help
- Synthesizing structured reactive programs via deterministic tree automata
- Properties of large 2-crossing-critical graphs
- Constant Congestion Brambles
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)
