Interval graphs and searching
From MaRDI portal
The interval thickness of a graph G is the minimum clique number of all the interval supergraphs of G. The clique number of a graph is the number of nodes of its biggest complete subgraph. On the other hand, the node- search number is the least number of searchers (pebbles) required to clear the contaminated edges of a graph. A contaminated edge is cleared by concurrently having two searchers on both of its endpoints. The contamination may spread from an uncleared edge to a cleared one through an unguarded path. It is proved that for any graph the node- search number is equal to the interval thickness.
Recommendations
Cites work
Cited in
(68)- Interval graphs and related topics
- Quickly excluding a forest
- Narrowness, pathwidth, and their application in natural language processing
- Excluding infinite minors
- The vertex separation number of a graph equals its path-width
- A partial k-arboretum of graphs with bounded treewidth
- On the pathwidth of chordal graphs
- Fugitive-search games on graphs and related parameters
- Helicopter search problems, bandwidth and pathwidth
- Interval degree and bandwidth of a graph
- On the monotonicity of games generated by symmetric submodular functions.
- Searching with mobile agents in networks with liars.
- Edge and node searching problems on trees
- Algorithms and obstructions for linear-width and related search parameters
- Step-wise tile assembly with a constant number of tile types
- Finite graph automata for linear and boundary graph languages
- Directed tree-width
- Approximate search strategies for weighted trees
- Connections between cutting-pattern sequencing, VLSI design, and flexible machines
- On tradeoffs between width- and fill-like graph parameters
- The inverse Voronoi problem in graphs. I: Hardness
- Metric dimension parameterized by treewidth
- Hardness of metric dimension in graphs of constant treewidth
- Parameterized complexity of \((A,\ell)\)-path packing
- Zero-visibility cops and robber and the pathwidth of a graph
- The theory of guaranteed search on graphs
- Imbalance is fixed parameter tractable
- Node-searching problem on block graphs
- On the interval completion of chordal graphs
- Graph searching and interval completion
- Mixed search number and linear-width of interval and split graphs
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Variable neighborhood search for the vertex separation problem
- Jumping robbers in digraphs
- Mixed Search Number of Permutation Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Edge search number of cographs
- scientific article; zbMATH DE number 1472189 (Why is no real title available?)
- The complexity of minimum-length path decompositions
- The pathwidth and treewidth of cographs
- A linear fixed parameter tractable algorithm for connected pathwidth
- Searching for a Visible, Lazy Fugitive
- Edge Search Number of Cographs in Linear Time
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- scientific article; zbMATH DE number 7651203 (Why is no real title available?)
- A 3-approximation for the pathwidth of Halin graphs
- Computing the vertex separation of unicyclic graphs
- Connected search for a lazy robber
- Fugitive-search games on graphs and related parameters
- Graph searching on chordal graphs
- A cops and robber game and the meeting time of synchronous directed walks
- Mixed searching and proper-path-width
- Pathwidth of 2-layer k-planar graphs
- Graph parameters, universal obstructions, and WQO
- Connected graph searching
- Complexity results for a cops and robber game on directed graphs
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- A linear-time approximation algorithm for the minimum-length geometric embedding of trees
- An overview of universal obstructions for graph parameters
- Monotone decontamination of arbitrary dynamic graphs with mobile agents
- Homomorphism indistinguishability and game comonads for restricted conjunction and requantification
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- How to hunt an invisible rabbit on a graph
- The complexity of zero-visibility cops and robber
- An annotated bibliography on guaranteed graph searching
- Distributed chasing of network intruders
- Maximum vertex occupation time and inert fugitive: Recontamination does help
This page was built for publication: Interval graphs and searching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1059088)
