Exclusive graph searching vs. pathwidth

DOI10.1016/j.ic.2016.11.007zbMath1355.68208OpenAlexW1195400218MaRDI QIDQ729824

Stéphane Pérennes, Nicolas Nisse, Euripides Markou

Publication date: 22 December 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.11.007

zbMATH Keywords

pathwidthgraph searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On the Cooperative Graph Searching Problem ⋮ Exclusive graph searching ⋮ Searching by heterogeneous agents

Cites Work

• Unnamed Item
• Edge search number of cographs
• Connected graph searching
• An annotated bibliography on guaranteed graph searching
• Graph minors. I. Excluding a forest
• Min Cut is NP-complete for edge weighted trees
• On the pathwidth of chordal graphs
• Graph searching on some subclasses of chordal graphs
• Approximating MIN 2-SAT and MIN 3-SAT
• Searching and pebbling
• A distributed algorithm for computing the node search number in trees
• Exclusive Graph Searching
• Mixed search number and linear-width of interval and split graphs
• Mixed Search Number of Permutation Graphs
• A Linear Recognition Algorithm for Cographs
• The complexity of searching a graph
• Monotonicity in graph searching
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• The Pathwidth and Treewidth of Cographs

This page was built for publication: Exclusive graph searching vs. pathwidth