✦ LIBER ✦

k-Path partitions in trees

✍ Scribed by Jing-Ho Yan; Gerard J. Chang; Sandra M. Hedetniemi; stephen T. Hedetniemi

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 437 KB
Volume: 78
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00012-7

No coin nor oath required. For personal study only.

✦ Synopsis

For 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 2path 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.

📜 SIMILAR VOLUMES

Partitions and normal trees

✍ Muhammad Ali McBeth; Rod McBeth 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 373 KB

The partitions of a natural number n (with parts taken in non-increasing order), may be listed in dictionary order. This ordering of partitions is shown to correspond to the post ordering of chains of a finite tree T[n]. It is shown that T[n] belongs to a, the class of normal trees. % occurs indepen

On the k-path partition of graphs

✍ George Steiner 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 150 KB

Integer Partitions and Binary Trees

✍ Frank Schmidt 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 82 KB

We present observations and problems connected with a weighted binary tree representation of integer partitions.  2002 Elsevier Science (USA)

On trees and noncrossing partitions

✍ Martin Klazar 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 426 KB

We give a simple and natural proof of (an extension of) the identity P(X. 1. )I ) = t-'2( X I. I -I. II --I ). The number P(li, I, 17) counts noncrossing partitions of { I, 2. I} unto II parts such that no part contains two numbers .Y and J'. O<.v --.v<k. The lower index 2 indicate\ partitions with

Efficient algorithms for path partitions

✍ Craig Williams; Dana Richards 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 763 KB

On partitions of graphs into trees

✍ F.R.K. Chung 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 934 KB

We crgnsider the minimum m\*-nber T(G) of subsets intl:, which the edge set E(G) of a graph G can lx partitioned so that each subset forms a tree. It is shown that for any connected (3 with II vertices, we always have T( Gj s [$I.