|
|
|
| Model and Algorithm Research for Seeking Efficient Monitor-Nodes
Measuring Network Traffic |
| Jiang Hong-yan; Lin Ya-ping; Huang Sheng-ye |
| College of Computer and Communication, Hunan University, Changsha 410082, China |
|
|
|
|
Abstract The problem of seeking monitor-nodes for measuring the network traffic is regarded as the problem of finding out the minimum weak vertex cover of a graph which is NP-hard. An approximation algorithm is proposed in this paper based on the concept of incidence matrix in Graph. Also the complexity of the algorithm is analyzed. Furthermore, the algorithm is expanded to seek the minimum weak vertex cover for a graph that has weights on the nodes. The theoretical analysis and the simulation results show that the novel algorithm is more scalable than the traditional algorithms, and can find smaller weak vertex cover.
|
|
Received: 29 November 2004
|
|
|
|
|
|
|
|
|
2006, Vol. 28 
