Geodesic
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 253-261.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: computational complexity, vertex ranking, spanning tree 
@article{DMGT_2009_29_2_a3,
     author = {Dereniowski, Dariusz},
     title = {Minimum vertex ranking spanning tree problem for chordal and proper interval graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {253--261},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a3/}
}
TY  - JOUR
AU  - Dereniowski, Dariusz
TI  - Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 253
EP  - 261
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a3/
LA  - en
ID  - DMGT_2009_29_2_a3
ER  - 
%0 Journal Article
%A Dereniowski, Dariusz
%T Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 253-261
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a3/
%G en
%F DMGT_2009_29_2_a3
Dereniowski, Dariusz. Minimum vertex ranking spanning tree problem for chordal and proper interval graphs. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 253-261. http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a3/

[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.

[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:4249::AID-NET5>3.0.CO;2-D

[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.

[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.

[6] D. Dereniowski and M. Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006) 273-285.

[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.

[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.

[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.

[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.

[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.