✦ LIBER ✦

Two Algorithms for Unranking Arborescences

✍ Scribed by Charles J. Colbourn; Wendy J. Myrvold; Eugene Neufeld

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 147 KB
Volume: 20
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0014

No coin nor oath required. For personal study only.

✦ Synopsis

Ž 3 . Colbourn, Day, and Nel developed the first algorithm requiring at most O n Ž arithmetic operations for ranking and unranking spanning trees of a graph n is the . number of vertices of the graph . We present two algorithms for the more general problem of ranking and unranking rooted spanning arborescences of a directed Ž 3 . graph. The first is conceptually very simple and requires O n arithmetic operations. The second approach shows that the number of arithmetic operations can be reduced to the same as that of the best known algorithms for matrix multiplication.

📜 SIMILAR VOLUMES

A strongly polynomial algorithm for the

A strongly polynomial algorithm for the inverse shortest arborescence problem

✍ Hu Zhiquan; Liu Zhenhong 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 909 KB

In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is. given a directed graph G and a set of nonnegative costs on its arcs. we need to modify those costs as little as possible to ensure that T, a given (.I-arborescence of G, is the shortest one. It is

Two algorithms for matroids

✍ Bradley Hull 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 962 KB

A branch-and-cut algorithm for the resou

A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem

✍ Fischetti, Matteo; Vigo, Daniele 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 2 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.

Algorithms for two bottleneck optimizati

Algorithms for two bottleneck optimization problems

✍ Harold N Gabow; Robert E Tarjan 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 435 KB

Two algorithms for the sieve method

✍ Herbert S Wilf 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 191 KB

On fast algorithms for two servers

✍ Marek Chrobak; Lawrence L Larmore 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 443 KB