Citation
D. Kuo et Gj. Chang, THE PROFILE MINIMIZATION PROBLEM IN TREES, SIAM journal on computing, 23(1), 1994, pp. 71-81
Citations number
9
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
00975397
Volume
23
Issue
1
Year of publication
1994
Pages
71 - 81
Database
ISI
SICI code
0097-5397(1994)23:1<71:TPMPIT>2.0.ZU;2-7
Abstract
The profile minimization problem is to find a one-to-one function f fr
om the vertex set V(G) of a graph G to the set of all positive integer
s 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.