# Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 253-261
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDariusz Dereniowski. "Minimum vertex ranking spanning tree problem for chordal and proper interval graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 253-261. <http://eudml.org/doc/270173>.

@article{DariuszDereniowski2009,

abstract = {A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.},

author = {Dariusz Dereniowski},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {computational complexity; vertex ranking; spanning tree},

language = {eng},

number = {2},

pages = {253-261},

title = {Minimum vertex ranking spanning tree problem for chordal and proper interval graphs},

url = {http://eudml.org/doc/270173},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Dariusz Dereniowski

TI - Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 253

EP - 261

AB - A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.

LA - eng

KW - computational complexity; vertex ranking; spanning tree

UR - http://eudml.org/doc/270173

ER -

## References

top- [1] A.S. Arefin and M.A. Kashem, NP-Completeness of the minimum edge-ranking spanning tree problem on series-parallel graphs, Proc. 10th International Conference on Computer and Information Technology, 2008 (ICCIT 2007) 1-4.
- [2] K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci. 13 (1976) 335-379, doi: 10.1016/S0022-0000(76)80045-1. Zbl0367.68034
- [3] D.Z. Chen, D. Lee, R. Sridhar and C.N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs, Networks 31 (1998) 249-257, doi: 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D Zbl1015.68054
- [4] J.S. Deogun, T. Kloks, D. Kratsch and H. Müller, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Appl. Math. 98 (1999) 39-63, doi: 10.1016/S0166-218X(99)00179-1. Zbl0937.68093
- [5] D. Dereniowski, Edge ranking and searching in partial orders, Discrete Appl. Math. 156 (2008) 2493-2500, doi: 10.1016/j.dam.2008.03.007. Zbl1152.68014
- [6] D. Dereniowski and M. Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006) 273-285. Zbl1098.68036
- [7] D. Dereniowski and A. Nadolski, Vertex rankings of chordal graphs and weighted trees, Inform. Process. Letters 98 (2006) 96-100, doi: 10.1016/j.ipl.2005.12.006. Zbl1187.68340
- [8] S.-Y. Hsieh, On vertex ranking of a starlike graph, Inform. Process. Letters 82 (2002) 131-135, doi: 10.1016/S0020-0190(01)00262-9.
- [9] M.A. Kashem, M.A. Haque, M.R. Uddin and S.A. Sharmin, An algorithm for finding minimum edge-ranking spanning tree of series-parallel graphs, Proc. of the 9th International Conference on Computer and Information Technology (ICCIT 2006) 108-112.
- [10] K. Makino, Y. Uno and T. Ibaraki, Minimum edge ranking spanning trees of threshold graphs, Lecture Notes in Comp. Sci. 2518 (2002) 59-77. Zbl1019.68079
- [11] K. Makino, Y. Uno and T. Ibaraki, On minimum edge ranking spanning trees, J. Algorithms 38 (2001) 411-437, doi: 10.1006/jagm.2000.1143. Zbl0974.68152
- [12] K. Miyata, S. Masuyama, S. Nakayama and L. Zhao, Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410, doi: 10.1016/j.dam.2006.04.016. Zbl1110.68111
- [13] S. Nakayama and S. Masuyama, An algorithm for solving the minimum vertex ranking spanning tree problem on interval graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E86-A (2003) 1019-1026.
- [14] S. Nakayama and S. Masuyama, A polynomial time algorithm for obtaining a minimum vertex ranking spanning tree in outerplanar graphs, IEICE Transactions on Information and Systems E89-D (2006) 2357-2363, doi: 10.1093/ietisy/e89-d.8.2357.
- [15] A. Pothen, The complexity of optimal elimination trees, Tech. Report CS-88-13, The Pennsylvania State University, 1988.
- [16] A.A. Schäffer, Optimal node ranking of trees in linear time, Inform. Process. Letters 33 (1989) 91-96, doi: 10.1016/0020-0190(89)90161-0.