Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 2 | 253-261
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Department of Algorithms and System Modeling, Gdańsk University of Technology, Poland
  • [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:4<249::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.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.