Full metadata record
DC FieldValueLanguage
dc.contributor.authorKUO, Den_US
dc.contributor.authorCHANG, GJen_US
dc.date.accessioned2014-12-08T15:04:08Z-
dc.date.available2014-12-08T15:04:08Z-
dc.date.issued1994-02-01en_US
dc.identifier.issn0097-5397en_US
dc.identifier.urihttp://hdl.handle.net/11536/2631-
dc.description.abstractThe 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.language.isoen_USen_US
dc.subjectSPARSE MATRIXen_US
dc.subjectPROFILEen_US
dc.subjectLABELINGen_US
dc.subjectTREEen_US
dc.subjectLEAFen_US
dc.subjectCENTROIDen_US
dc.subjectBASIC PATHen_US
dc.subjectALGORITHMen_US
dc.titleTHE PROFILE MINIMIZATION PROBLEM IN TREESen_US
dc.typeArticleen_US
dc.identifier.journalSIAM JOURNAL ON COMPUTINGen_US
dc.citation.volume23en_US
dc.citation.issue1en_US
dc.citation.spage71en_US
dc.citation.epage81en_US
dc.contributor.department交大名義發表zh_TW
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentNational Chiao Tung Universityen_US
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:A1994MZ11700006-
dc.citation.woscount17-
Appears in Collections:Articles


Files in This Item:

  1. A1994MZ11700006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.