THE PROFILE MINIMIZATION PROBLEM IN TREES
檔案
- A1994MZ11700006.pdf (820.6 KB, Adobe PDF)
日期
1994-02-01
類型
期刊名稱
SIAM JOURNAL ON COMPUTING
卷期與頁次
第 23 卷第 1 期,頁 71–81
ISSN
0097-5397
語言
英文
摘要
The profile minimization problem is to find a one-to-one function f from the vertex set V(G) of a graph G to the set of all positive integers such that SIGMA(x is-an-element-of V(G)){(f(x) - min(y is-an-element-of N[x]) f(y)} is as small as possible, where N[x] = {x} or {y : y is adjacent to x} is the closed neighborhood of x in G. This paper gives an O(n1.722) time algorithm for the problem in a tree of n vertices.