𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimality of consecutive and nested tree partitions

✍ Scribed by Chang, G. J.; Hwang, F. K.

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
84 KB
Volume
30
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called consecutive partitions and nested partitions, have been well studied for the set partition problem, which is a special case of the tree-partition problem when the tree is a path. We give conditions on the optimality of these classes on tree partitions and also extend our results to tree networks.

πŸ“œ SIMILAR VOLUMES

Enumerating Consecutive and Nested Parti
Enumerating Consecutive and Nested Partitions for Graphs
✍ F.K. Hwang; G.J. Chang πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 116 KB

Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. We extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph. A subset of vertices is conside

Optimal consecutive-2 systems of lines a
Optimal consecutive-2 systems of lines and cycles
✍ D. Z. Du; F. K. Hwang πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 355 KB

A consecutive-2 system is a graph where each vertex can either work or fail and the system fails if and only if two vertices incident to the same edge both fail. The simplest probability structure attached to such systems is to assume that vertex i has probability p, of failing and the states of the

Nests, tree holes, and the evolution of
Nests, tree holes, and the evolution of primate life histories
✍ Peter M. Kappeler πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 513 KB

In contrast to the majority of primates, many prosimians, some New World monkeys, and the great apes rest in tree holes or self-constructed nests during their inactive periods. The goal of this comparative study was to examine possible functions of this interspecific variation. Information on restin

A correction to β€œAgent searching in a tr
A correction to β€œAgent searching in a tree and the optimality of iterative deepening”
✍ Pallab Dasgupta; P.P. Chakrabarti; S.C. DeSarkar πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 229 KB

This paper contains a correction to one of the results presented in an earlier work [ 21 and establishes a new result in that direction. In the paper entitled "Agent searching in a tree and the optimality of iterative deepening" [2] we had presented three independent results, namely that there exist