演講題目：On the Minimum Graph Searching Spanning Tree Problem
主講人：彭勝龍 教授(東華大學資訊工程學系教授)
時間：105年3月30日(星期三13：30 - 15：00)
地點：文1F10
Abstract:
For a graph G = (V, E), the graph searching problem on G is to determine the minimum number of searchers to clean G via the searching rules. It is studied for a long time and in particular, three variants, namely, node searching, edge searching, and mixed searching, are well studied. In this talk, we propose the minimum graph searching spanning tree problem on G. The objective is to find a spanning tree T of G such that the search number of T is the minimum among all possible spanning trees of G. We show the NP-hardness of for the three versions of the graph searching spanning tree problem and propose approximation algorithms for each searching spanning tree problem.
