𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum-weight two-connected spanning networks

✍ Scribed by Clyde L. Monma; Beth Spellman Munson; William R. Pulleyblank

Publisher
Springer-Verlag
Year
1990
Tongue
English
Weight
984 KB
Volume
46
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Counting Minimum Weight Spanning Trees
Counting Minimum Weight Spanning Trees
✍ Andrei Z. Broder; Ernst W. Mayr πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 152 KB

We present an algorithm for counting the number of minimum weight spanning trees, based on the fact that the generating function for the number of spanning trees of a given graph, by weight, can be expressed as a simple determinant. For a graph with n vertices and m edges, our Ε½ Ε½ .. Ε½ . algorithm r

On finding a minimum spanning tree in a
On finding a minimum spanning tree in a network with random weights
✍ Colin McDiarmid; Theodore Johnson; Harold S. Stone πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 221 KB πŸ‘ 2 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e Ε½ . have independent identically distributed random weights w e . We find that when the kth ' Ε½ . edge e is added to the current tree

Minimum-weight rooted not-necessarily-sp
Minimum-weight rooted not-necessarily-spanning arborescence problem
✍ V. Venkata Rao; R. Sridharan πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 687 KB

## Abstract In this paper, we propose the problem of identifying a minimum‐weight rooted not‐necessarily‐spanning arborescence (MRA) in a directed rooted acyclic graph with weights on arcs. We show this problem to be NP‐hard and formulate it as a zeroβ€”one integer program. We develop a heuristic __H