On the domination search number

DOI10.1016/S0166-218X(02)00389-XMaRDI QIDQ1811076zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Dieter Kratsch, Haiko Müller

Publication date 10 June 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(02)00389-x

zbMATH Keywords

dominationasteroidal triple-free graphgraph searchingdominating target

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 1696531
• Graph-Theoretic Concepts in Computer Science
• Distance \(d\)-domination games
• Approximation algorithms for domination search
• Complexity and monotonicity results for domination games

Cites work

• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• scientific article; zbMATH DE number 1151792 (Why is no real title available?)
• scientific article; zbMATH DE number 1164584 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 4183231 (Why is no real title available?)
• An algorithm for searching a polygonal region with a flashlight
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Eavesdropping games
• Efficient probabilistically checkable proofs and applications to approximations
• Fugitive-search games on graphs and related parameters
• Graph Classes: A Survey
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and interval completion
• Helicopter search problems, bandwidth and pathwidth
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Min Cut is NP-complete for edge weighted trees
• Monotonicity in graph searching
• On minimizing width in linear layouts
• On some problems of guaranteed search
• On the hardness of approximating minimization problems
• On the structure of graphs with bounded asteroidal number
• Optimal Algorithms for a Pursuit-Evasion Problem in Grids
• Optimal numberings and isoperimetric problems on graphs
• Recontamination does not help to search a graph
• SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER
• SEARCHING FOR A MOBILE INTRUDER IN A CORRIDOR —THE OPEN EDGE VARIANT OF THE POLYGON SEARCH PROBLEM
• Searching and pebbling
• Searching for a Mobile Intruder in a Polygonal Region
• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
• The bandwidth problem for graphs and matrices—a survey
• The vertex separation and search number of a graph
• Topological Bandwidth

Cited in

(6)

• Complexity and monotonicity results for domination games
• An annotated bibliography on guaranteed graph searching
• Graph-Theoretic Concepts in Computer Science
• DAG-width is PSPACE-complete
• scientific article; zbMATH DE number 1696531 (Why is no real title available?)
• Approximation algorithms for domination search

This page was built for publication: On the domination search number

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