Full metadata record
DC FieldValueLanguage
dc.contributor.authorYan, JHen_US
dc.contributor.authorChang, GJen_US
dc.contributor.authorHedetniemi, SMen_US
dc.contributor.authorHedetniemi, STen_US
dc.date.accessioned2014-12-08T15:01:23Z-
dc.date.available2014-12-08T15:01:23Z-
dc.date.issued1997-10-21en_US
dc.identifier.issn0166-218Xen_US
dc.identifier.urihttp://hdl.handle.net/11536/248-
dc.description.abstractFor a fixed positive integer k, the k-path partition problem is to partition the vertex set of a graph into the smallest number of paths such that each path has at most k vertices. The 2-path partition problem is equivalent to the edge-cover problem. This paper presents a linear-time algorithm for the k-path partition problem in trees. The algorithm is applicable to the problem of finding the minimum number of message originators necessary to broadcast a message to all vertices in a tree network in one or two time units.en_US
dc.language.isoen_USen_US
dc.titlek-path partitions in treesen_US
dc.typeArticleen_US
dc.identifier.journalDISCRETE APPLIED MATHEMATICSen_US
dc.citation.volume78en_US
dc.citation.issue1-3en_US
dc.citation.spage227en_US
dc.citation.epage233en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:A1997YC69500017-
dc.citation.woscount9-
Appears in Collections:Articles


Files in This Item:

  1. A1997YC69500017.pdf