Browsing by Author "KUO, D"

Now showing 1 - 1 of 1

THE PROFILE MINIMIZATION PROBLEM IN TREES
(1994-02-01)
KUO, D
;
CHANG, GJ
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
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.