| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421482 | Discrete Applied Mathematics | 2006 | 9 Pages |
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)(⌈Ds/2⌉+1)/(⌊log2(Ds+1)⌋+1)-approximation algorithm for MVRST where DsDs is the minimum diameter of spanning trees of G.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Keizo Miyata, Shigeru Masuyama, Shin-ichi Nakayama, Liang Zhao,