PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 4 | 725-735
Tytuł artykułu

Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
For a graph G = (V, E), a function f:V(G) → {1,2, ...,k} is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, $ψ_r(G)$, of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.
Wydawca
Rocznik
Tom
32
Numer
4
Strony
725-735
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-06-20
poprawiono
2011-12-20
zaakceptowano
2011-12-29
Twórcy
  • Anderson University, Anderson, SC 29621, USA
autor
  • School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
  • Department of Mathematical Sciences, Clemson University, Clemson SC 29634, USA
  • School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
autor
  • Bally Technologies, USA
Bibliografia
  • [1] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller and Zs. Tuza, Rankings of graphs, Graph-theoretic concepts in computer science (Herrsching, 1994), Lect. Notes Comput. Sci. 903 (1995) 292-304.
  • [2] P.De la Torre, R. Greenlaw and A. Schaeffer, Optimal ranking of trees in polynomial time, In: Proc. 4^{th} ACM Symp. on Discrete Algorithms, Austin Texas, (1993) 138-144.
  • [3] I.S. Duff and J.K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software (1983) 9 302-325, doi: 10.1145/356044.356047.
  • [4] J. Ghoshal, R. Laskar and D. Pillone, Minimal rankings, Networks 28 ( 1996) 45-53, doi: 10.1002/(SICI)1097-0037(199608)28:1<45::AID-NET6>3.0.CO;2-D
  • [5] J. Ghoshal, R. Laskar and D. Pillone, Further results on minimal rankings, Ars Combin. 52 (1999) 181-198.
  • [6] S. Hsieh, On vertex ranking of a starlike graph, Inform. Process. Lett. 82 (2002) 131-135, doi: 10.1016/S0020-0190(01)00262-9.
  • [7] A.V. Iyer, H.D. Ratliff and G. Vijayan, Optimal node ranking of trees, Inform. Process. Lett. 28 (1988) 225-229, doi: 10.1016/0020-0190(88)90194-9.
  • [8] V. Kostyuk, D.A. Narayan and V.A. Williams, Minimal rankings and the arank number of a path, Discrete Math. 306 (2006) 1991-1996, doi: 10.1016/j.disc.2006.01.027.
  • [9] R. Laskar and D. Pillone, Theoretical and complexity results for minimal rankings, J. Combin. Inform. System Sci. 25) (2000) 17-33.
  • [10] R. Laskar and D. Pillone, Extremal results in rankings, Congr. Numer. 149 (2001) 33-54.
  • [11] C. Leiserson, Area efficient graph layouts for VLSI, Proc. 21st Ann IEEE Symp. FOCS (1980) 270-281.
  • [12] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11 (1990) 134-172, doi: 10.1137/0611010.
  • [13] S. Novotny, J. Ortiz and D.A. Narayan, Minimal k-rankings and the rank number of P²ₙ, Inform. Process. Lett. 109 (2009) 193-198, doi: 10.1016/j.ipl.2008.10.004.
  • [14] A. Sen, H. Deng and S. Guha, On a graph partition problem with application to VLSI layout, Inform. Process. Lett. 43 (1992) 87-94, doi: 10.1016/0020-0190(92)90017-P.
  • [15] X. Zhou, N. Nagai and T. Nishizeki, Generalized vertex-rankings of trees, Inform. Process. Lett. 56 (1995) 321-328, doi: 10.1016/0020-0190(95)00172-7.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1634
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ć.