THE PROFILE MINIMIZATION PROBLEM IN TREES
| dc.citation.epage | 81 | en_US |
| dc.citation.issue | 1 | en_US |
| dc.citation.spage | 71 | en_US |
| dc.citation.volume | 23 | en_US |
| dc.citation.woscount | 17 | |
| dc.contributor.author | KUO, D | en_US |
| dc.contributor.author | CHANG, GJ | en_US |
| dc.contributor.department | 交大名義發表 | zh_TW |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | National Chiao Tung University | en_US |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:04:08Z | |
| dc.date.available | 2014-12-08T15:04:08Z | |
| dc.date.issued | 1994-02-01 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.issn | 0097-5397 | en_US |
| dc.identifier.journal | SIAM JOURNAL ON COMPUTING | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/2631 | |
| dc.identifier.wosnumber | WOS:A1994MZ11700006 | |
| dc.language.iso | en_US | en_US |
| dc.subject | SPARSE MATRIX | en_US |
| dc.subject | PROFILE | en_US |
| dc.subject | LABELING | en_US |
| dc.subject | TREE | en_US |
| dc.subject | LEAF | en_US |
| dc.subject | CENTROID | en_US |
| dc.subject | BASIC PATH | en_US |
| dc.subject | ALGORITHM | en_US |
| dc.title | THE PROFILE MINIMIZATION PROBLEM IN TREES | en_US |
| dc.type | Article | en_US |