Name
Abstract | ||
|---|---|---|
Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2006.04.018 | Discrete Applied Mathematics |
Keywords | Field | DocType |
non-trivial graph class,general graph,threshold graph,edge ranking,tree problem,graph g,polynomial time algorithm,linear time,minimum edge ranking,problem merst,split graph,spanning tree | Discrete mathematics,Combinatorics,Indifference graph,Tree-depth,Chordal graph,Spanning tree,Pathwidth,Longest path problem,Mathematics,Minimum spanning tree,Split graph | Journal |
Volume | Issue | ISSN |
154 | 16 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuhisa Makino | 1 | 1088 | 102.74 |
| yushi uno | 2 | 222 | 28.80 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |