✦ LIBER ✦

On a tree-cutting problem of P. Ash

✍ Scribed by I. Krasikov

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 597 KB
Volume: 93
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90216-o

No coin nor oath required. For personal study only.

✦ Synopsis

Krasikov, I., On a tree-cutting problem of P. Ash, Discrete Mathematics 93 (1991) 55-61. It is shown that in every tree T with N vertices, there are k vertices such that the connected components obtained by deleting those k vertices can be partitioned into two classes C;k and Ci with Moreover, for each k there is an infinite family of trees, namely, ternary trees, with the optimal value of &(T) equal to -2(&l).

We also consider the corresponding question for the edge deletion.

📜 SIMILAR VOLUMES

The generalized P-forest problem on a tr

The generalized P-forest problem on a tree network

✍ Arie Tamir; Timothy J. Lowe 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 665 KB

On stochastic spanning tree problem

✍ S. Geetha; K. P. K. Nair 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 443 KB

This paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objective is to find a spectrum of optimal spanning trees satisfying a certain chance constraint whose right-hand side also is treated as a decision variable. A special

The preemptive swapping problem on a tre

The preemptive swapping problem on a tree

✍ Shoshana Anily; Michel Gendreau; Gilbert Laporte 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 237 KB 👁 1 views

A polynomial algorithm for thep-centdian

A polynomial algorithm for thep-centdian problem on a tree

✍ Tamir, Arie; P�rez-Brito, Dionisio; Moreno-P�rez, Jos� A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

The most common problems studied in network location theory are the p-median and the p-center models. The p-median problem on a network is concerned with the location of p points (medians) on the network, such that the total (weighted) distance of all the nodes to their respective nearest points is

On a tree-shaped facility location probl

On a tree-shaped facility location problem of Minieka

✍ Ramon Rabinovitch; Arie Tamir 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 277 KB 👁 1 views

The minimax multistop location problem o

The minimax multistop location problem on a tree

✍ O. Berman; D. Simchi-Levi; A. Tamir 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 580 KB