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

Dariusz Dereniowski

Discussiones Mathematicae Graph Theory (2009)

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

Abstract

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

How to cite

top

Dariusz 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. [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. [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. [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. [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. [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. [6] D. Dereniowski and M. Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006) 273-285. Zbl1098.68036
  7. [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. [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. [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. [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. [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. [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. [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. [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. [15] A. Pothen, The complexity of optimal elimination trees, Tech. Report CS-88-13, The Pennsylvania State University, 1988. 
  16. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.