|
|||||
|
|
Minimum edge ranking spanning trees of split graphs |
|
| Authors: | Kazuhisa Makino Toshihide Ibaraki |
| Institution: | a Department of Mathematical Informatics, Graduate School of Information and Technology, University of Tokyo, Tokyo 113-8656, Japan b Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University, Sakai 599-8531, Japan c Department of Informatics, School of Science and Technology, Kwansei Gakuin University, Sanda 669-1337, Japan |
| 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. |
| Keywords: | 68R10 05C85 |
| 本文献已被 ScienceDirect 等数据库收录！ | |