中文摘要
合格證明
Table of contents
Abstract
Acknowledgements
1. Introduction
2. Single step graph searching problem
2.1 The single step graph searching problem vs the maximum 2-independe -t set problem
2.2 Complexities about solving the single step graph searching problem on special graphs
2.3 Summary
3. General weighted single step graph searching problem
3.1 General weighted single step graph searching problems
3.2 Problem complexities
3.3 A linear time algorithm for solving the S-type problem on trees
3.4 Reduction from the B-type problem to the S-type porblem
3.5 Solving the H-type problem on trees
3.6 Decision rules A
3.7 Decision rules B
3.8 Summary
4 Weighted single step graph searching priblem)extra searchers only)
4.1 Problem complexities
4.2 Basic properties of block graphs
4.3 A Linear time algorithm for solving the S-type problem on block graphs
4.4 The B-tyep problem on block graphs
4.5 Solving the H-type problem on block graphs
4.6 Summary
5 Solving the weighted single step graph searching problem extrasearchers only on interval graphs
5.1 Solving the S-type problem on weighted interval graphs
5.2 Solving the B-type problem on weighted interval graphs
5.3 Solving the H-type problem on weighted interval graphs
5.4 Summary
6 Concluding remarks and future research directions
6.1 Conclusions
6.2 Future research directions
References