|
|||||
|
|
Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem |
|
| Authors: | Keizo Miyata Shin-ichi Nakayama |
| Affiliation: | a Knowledge-Based Information Engineering, Toyohashi University of Technology, Toyohashi 441-8580, Japan b Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima, Tokushima 770-8502, Japan c Department of Information Science, Faculty of Engineering, Utsunomiya University, Utsunomiya 321-8585, Japan |
| Abstract: | The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈Ds/2⌉+1)/(⌊log2(Ds+1)⌋+1)-approximation algorithm for MVRST where Ds is the minimum diameter of spanning trees of G. |
| Keywords: | Vertex ranking Spanning tree Graph theory NP-hard Computational complexity Approximation algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |