李德財臺灣大學：資訊工程學研究所葉恆青Yeh, HengchinHengchinYeh2007-11-262018-07-052007-11-262018-07-052003http://ntur.lib.ntu.edu.tw//handle/246246/53896In this thesis we have studied the reporting center problem for interval graphs and trees. The reporting center problem is first introduced in the wireless network field, in which the reporting center strategy is used as one of the strategies for tracking mobile users, and aims at balancing the cost of updating the user position and the cost of locating a mobile user. The reporting center strategy partitions the cellular network into reporting and non-reporting cells. Associated with each reporting cell is a set of non-reporting cells, called its vicinity. Mobile users report their position only when they visit a reporting cell. When a call arrives, the user is searched for only in the vicinity of the last visited reporting center. The size of the vicinity of a reporting center determines the searching and updating cost of the cellular network. It is thus an objective to minimize the number of reporting centers subject to the constraint that the size of the vicinity of each reporting center is bounded by a constant Z>0. The problem has been shown to be NP-hard for arbitrary graphs for Z >= 2. The major contribution of this work is divided into two parts: (1) an algorithm that solves the reporting center problem for arbitrary vicinity for interval graphs, thereby improving a previous result which only solves for vicinity Z=2 for interval graphs and for arbitrary vicinity for proper interval graphs, and (2) an O(n) time algorithm that solves the reporting center problem for trees, which is better than the previous $O(nZ^3)$ result.1 Introduction 1 2 Reporting Center Problem for Interval Graphs 5 2.1 The Staircase Method 5 2.2 Bricks Transformation Method 28 3 Reporting Center Problem for Trees 31 4.Conclusion 53 5.Bibliography 55en-US通報中心問題圖論Reporting CenterTreeInterval Graphthesis