๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Efficient Algorithm for Minimum-Weight Bibranching

โœ Scribed by J. Keijsper; R. Pendavingh

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
280 KB
Volume
73
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

โœฆ Synopsis

Given a directed graph D=(V, A) and a set S V, a bibranching is a set of arcs B A that contains a v&(V "S) path for every v # S and an S&v path for every v # V "S. In this paper, we describe a primal dual algorithm that determines a minimum weight bibranching in a weighted digraph. It has running time O(n$(m+n log n)), where m= |A|, n=|V| and n$=min[ |S|, |V "S| ]. Thus, our algorithm obtains the best known bounds for two important special cases of the problem: bipartite edge cover and r-branching.

๐Ÿ“œ SIMILAR VOLUMES

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.

An efficient algorithm for parallel inte
An efficient algorithm for parallel integer multiplication
โœ Benjamin Singer; George Saon ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 67 KB

In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memoryresident lookup table dedicated to squares. Such an operator called PIM (parallel integer multiplication) is in fact microprogrammed at t