Name
Abstract | ||
|---|---|---|
In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree
of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show
that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case
performance ratio
\fracmin{ (D</font
>* -</font
> 1)logn/D</font
>* ,D</font
>* -</font
> 1} log(D</font
>* + 1) -</font
> 1
\frac{{\min \{ (\Delta ^* - 1)\log n/\Delta ^* ,\Delta ^* - 1\} }}
{{\log (\Delta ^* + 1) - 1}}
, where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination
of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the
analysis is based on novel properties of the edge ranking of trees.
|
Year | DOI | Venue |
|---|---|---|
1999 | 10.1006/jagm.2000.1143 | Mathematical Foundations of Computer Science |
Keywords | DocType | Volume |
existing algorithm,minimum edge,maximum degree,ranking problem,tree problem,edge ranking,graph g,minimum edge ranking spanning,approximation algorithm,problem merst,minimum edge ranking,spanning tree,polynomial time | Conference | 38 |
Issue | ISSN | ISBN |
2 | 0196-6774 | 3-540-66408-4 |
Citations | PageRank | References |
13 | 0.82 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuhisa Makino | 1 | 1088 | 102.74 |
| yushi uno | 2 | 222 | 28.80 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |