河內圖之最小邊排列編號

The Minimum Edge Ranking on Sierpinski S(n, 3) Graphs

陳穎治(Ying-Jhih Chen)

指導教授 ： 阮夙姿

共同指導教授 ： 王有禮(Yu-Le Wang)

國立暨南國際大學/科技學院/資訊工程學系/碩士(2009年)

摘要

一個圖在邊e上的邊編號r(e)是一個正整數，使得兩不同邊ei和 ej邊的編號r(ei) = r(ej)，則在ei和ej之間的每一個路徑上，都存在一邊ew且r(ew) > r(ei) = r(ej)。令一個圖的邊編號中最大的號碼為q，我們說一個圖的最小邊編號p，即是所有給定邊編號圖中的最大號碼q為最小的，此時p等於q。一個Sierpinski圖S(n, k)的點集合，是包含在整數1, 2, …, k的n多元組。我們說一個邊編號問題，是求最小邊編號。目前該問題，已被證明是NP-hard，非trivial的類別只有在樹和二連接外平面的圖上，才有多項式時間演算法。我的演算法是第一個在S(n, 3)求最小邊編號p的O(1)時間的演算法。

關鍵字

邊排列編號 ； 最小邊排列編號 ； 謝爾賓斯基圖 ； NP-hard ； 樹 ； 外平面的

並列摘要

Let e be an edge in a graph G. The labeling of e, denoted by r(e), is a positive integer. An edge ranking of graph G is a labeling of edges such that every path between two different edges ei, ej with r(ei) = r(ej) contains an intermediate edge ew with r(ew) > r(ei). An edge ranking is called a minimum edge ranking of G if its largest rank is minimum among all rankings of G. The edge ranking problem is to find a minimum edge ranking of graph G. The problem has been proved to be an NP-hard problem. It is known that there are polynomial time algorithms for non-trivial classes, such as trees and two-connected outerplanar graphs. Our algorithm is an O(1) time algorithm to find the minimum edge ranking on S(n, 3) graphs where S(n, k) is a Sierpinski graph consisting of all n-tuples of integers 1, 2, . . . , k.

並列關鍵字

edge ranking ； minimum edge ranking ； Sierpinski graph ； NP-hard ； tree ； outerplanar

參考文獻

[1] B. Aspvall, P. Heggernes, Finding minimum height elimination tree for interval graphs in polynomial time, BIT 34 (1994) 484– 509.

[2] D. Berend, A. Sapir, The diameter of Hanoi graphs, Inform. Process. Lett. 98 (2006) 79–85.

[3] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Z. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1) (1998) 168–181.

[4] J.S. Deogun, T. Kloks, D. Kratsch, H.Müller, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Appl. Math. 98 (1999) 39–63.

[5] S. Gravier, S. Klavˇ zar, M. Mollard, Codes and L(2, 1)-labelings in Sierpi ´ nski graphs, Taiwanese J. Math. 9 (2005) 671–681.