Exclusive graph searching vs. pathwidth

DOI10.1016/J.IC.2016.11.007MaRDI QIDQ729824zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Exclusive graph searching
• Exclusive graph searching
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 176249
• Fugitive-search games on graphs and related parameters

Cites work

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

Cited in

(3)

• Exclusive graph searching
• On the Cooperative Graph Searching Problem
• Exclusive graph searching

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729824)