Exclusive graph searching vs. pathwidth
Fecha
2017Language
en
Materia
Resumen
In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. © 2016 Elsevier Inc.
Colecciones
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Online graph exploration with advice
Dobrev, S.; Královič, R.; Markou, E. (2012)We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visiting a ... -
Knowledge distillation on neural networks for evolving graphs
Antaris S., Rafailidis D., Girdzijauskas S. (2021)Graph representation learning on dynamic graphs has become an important task on several real-world applications, such as recommender systems, email spam detection, and so on. To efficiently capture the evolution of a graph, ... -
Different speeds suffice for rendezvous of two agents on arbitrary graphs
Kranakis E., Krizanc D., Markou E., Pagourtzis A., Ramírez F. (2017)We consider the rendezvous problem for two robots on an arbitrary connected graph with n vertices and all its edges of length one. Two robots are initially located on two different vertices of the graph and can traverse ...