Reporting Center Problem for Interval Graphs and Trees
Date Issued
2003
Date
2003
Author(s)
Yeh, Hengchin
DOI
en-US
Abstract
In 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.
Subjects
通報中心問題
圖論
Reporting Center
Tree
Interval Graph
Type
thesis