On the domination search number

DOI10.1016/S0166-218X(02)00389-XzbMATH Open1019.68076DBLPjournals/dam/FominKM03OpenAlexW1993495807WikidataQ60488777 ScholiaQ60488777MaRDI QIDQ1811076FDOQ1811076

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)