On the domination search number

DOI10.1016/S0166-218X(02)00389-XzbMath1019.68076OpenAlexW1993495807WikidataQ60488777 ScholiaQ60488777MaRDI QIDQ1811076

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

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

dominationdominating targetasteroidal triple-free graphgraph searching

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)

Related Items

Complexity and monotonicity results for domination games, DAG-width is PSPACE-complete, An annotated bibliography on guaranteed graph searching

Cites Work

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