𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Heuristics for finding a maximum number of disjoint bounded paths

✍ Scribed by D. Ronen; Y. Perl

Publisher
John Wiley and Sons
Year
1984
Tongue
English
Weight
684 KB
Volume
14
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the following problem: Given an integer k and a network G with two distinct vertices s and t , find a maximum number of vertex disjoint paths from s to t of length bounded by k. In a recent work [ 91 it was shown that for length greater than four this problem is NP-hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved t o give optimal solution for length less than five. Experiments show very good results for the algorithm.

πŸ“œ SIMILAR VOLUMES

Efficient Algorithms for Finding the Max
Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
✍ Wun-Tat Chan; Francis Y.L. Chin πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 366 KB

In a rectangular grid, given two sets of nodes, S S sources and T T sinks , of size 2 Ε½ . each, the disjoint paths DP problem is to connect as many nodes in S S to the Ε½ nodes in T T using a set of ''disjoint'' paths. Both edge-disjoint and Β¨ertex-disjoint . cases are considered in this paper. Note

A new heuristic algorithm for finding mi
A new heuristic algorithm for finding minimum-cost multicast trees with bounded path delay
✍ Anna HaΔ‡; Kelei Zhou πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 246 KB

## This article presents a new heuristic algorithm called DDBMA (Dynamic Delay Bounded Multicast Algorithm) to construct a minimum-cost multicast tree. The heuristic depends on (1) bounded delay along paths from source nodes to each destination node; (2) minimum cost of the multicast tree; (3) dyn