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)- Refining a tree-decomposition which distinguishes tangles
- scientific article; zbMATH DE number 1104337 (Why is no real title available?)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Treewidth is a lower bound on graph gonality
- Canonical tree-decompositions of finite graphs. II. Essential parts
- Treewidth of graphs with balanced separations
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Cops and robber on oriented graphs with respect to push operation
- Non-deterministic graph searching in trees
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Complexity and monotonicity results for domination games
- Tangle and Maximal Ideal
- On the gonality of Cartesian products of graphs
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Constructing tree decompositions of graphs with bounded gonality
- scientific article; zbMATH DE number 176249 (Why is no real title available?)
- The pebbling threshold of the square of cliques
- Are there any good digraph width measures?
- Pursuing a fast robber on a graph
- Fugitive-search games on graphs and related parameters
- Directed path-decompositions
- 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
- DAG-width and circumference of digraphs
- Localization game on geometric and planar graphs
- A cop and robber game on edge-periodic temporal graphs
- Graphs without large apples and the maximum weight independent set problem
- Submodular partition functions
- Tree sets
- On tradeoffs between width- and fill-like graph parameters
- Tree-Width for First Order Formulae
- 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
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- Mathematical Foundations of Computer Science 2005
- An annotated bibliography on guaranteed graph searching
- Uniform Constraint Satisfaction Problems and Database Theory
- Graph searching with advice
- A unified treatment of linked and lean tree-decompositions
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Maximum vertex occupation time and inert fugitive: Recontamination does help
- The cordiality game and the game cordiality number
- Synthesizing structured reactive programs via deterministic tree automata
- Searching for a Visible, Lazy Fugitive
- Bounds on vertex colorings with restrictions on the union of color classes
- Properties of large 2-crossing-critical graphs
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Treewidth lower bounds with brambles
- Polynomial treewidth forces a large grid-like-minor
- A branch-and-price-and-cut method for computing an optimal bramble
- Constant Congestion Brambles
- On the maximum cardinality search lower bound for treewidth
- Connected tree-width
- Contraction obstructions for connected graph searching
- On the monotonicity of process number
- A two-person game on graphs where each player tries to encircle his opponent's men
- A robber locating strategy for trees
- The mixed search game against an agile and visible fugitive is monotone
- Cooperative exploration and protection of a workspace assisted by information networks
- A cops and robber game and the meeting time of synchronous directed walks
- Digraph Decompositions and Monotonicity in Digraph Searching
- Graph Searching in a Crime Wave
- Monotonicity of Non-deterministic Graph Searching
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- \(K_{6}\) minors in large 6-connected graphs
- On the complexity of planning for agent teams and its implications for single agent planning
- Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
- Directed tree-width
- Bounding the search number of graph products
- Entanglement and the complexity of directed graphs
- Parameterized pursuit-evasion games
- Integer programming models and algorithms for the graph decontamination problem with mobile agents
- Quickly excluding a forest
- Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
- Monotonicity of non-deterministic graph searching
- Digraph searching, directed vertex separation and directed pathwidth
- Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
- Monotony properties of connected visible graph searching
- LIFO-search on digraphs: a searching game for cycle-rank
- Constant congestion brambles in directed graphs
- Lower bounds for treewidth of product graphs
- Cops and robber on butterflies and solid grids
- Edge-treewidth: algorithmic and combinatorial properties
- Variations of cops and robbers game on grids
- Undirected Graphs of Entanglement 2
- Visibility graphs, dismantlability, and the cops and robbers game
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Adapting the directed grid theorem into an FPT algorithm
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- On low tree-depth decompositions
- On the treewidth of toroidal grids
- Parameters tied to treewidth
- Digraph width measures in parameterized algorithmics
- Treewidth of the line graph of a complete graph
- Hypertree-width and related hypergraph invariants
- Lower bounds on the pathwidth of some grid-like graphs
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)
