Full metadata record
DC FieldValueLanguage
dc.contributor.authorCHANG, YCen_US
dc.contributor.authorHSU, LHen_US
dc.date.accessioned2014-12-08T15:03:34Z-
dc.date.available2014-12-08T15:03:34Z-
dc.date.issued1995-01-13en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/11536/2103-
dc.description.abstractLet G = (V,E) be a graph. We associate with each edge e(i) is an element of E an ordered pair of rational numbers (a(i), b(i)). Let the weight of a spanning tree T, w(T), be defined as Sigma(ei is an element of T) a(i) + Pi(ei is an element of T) b(i). A spanning tree T in G is called a w-optimum spanning tree if w(T) greater than or equal to w(T') for all spanning trees T' in G. The function w is one instance in a class of two-parameter objectives. Hassin and Tamir proposed a unified approach for solving the class of two-parameter objective optimum spanning tree problems. Let s be an objective in the class and F-s(G) denote the weight of the s-optimum spanning tree of G. The element perturbation problem of the s-optimum spanning tree is to compute F-s(G - e(k)) for all e(k) is an element of E. With Hassin and Tamir's approach, let t(s)(p, q) be the complexity of computing the s-optimum spanning tree where p = V and q = E. In this paper, we present an approach to solve the element perturbation problem of the s-optimum spanning tree in t(s)(p, q).en_US
dc.language.isoen_USen_US
dc.subjectCOMBINATORIAL ALGORITHMSen_US
dc.subjectCOMPLEXITYen_US
dc.subjectSPANNING TREESen_US
dc.subjectMATROIDen_US
dc.titleELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVESen_US
dc.typeArticleen_US
dc.identifier.journalINFORMATION PROCESSING LETTERSen_US
dc.citation.volume53en_US
dc.citation.issue1en_US
dc.citation.spage55en_US
dc.citation.epage59en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:A1995QA31100009-
dc.citation.woscount0-
Appears in Collections:Articles


Files in This Item:

  1. A1995QA31100009.pdf