𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the reliable connectivity problem

✍ Scribed by Dimitris Kavadias; Lefteris M. Kirousis; Paul Spirakis

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
1015 KB
Volume
39
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The computational complexity of the reli
The computational complexity of the reliability problem on distributed systems
✍ Min-Sheng Lin; Deng-Jyi Chen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 450 KB

The reliability of a distributed program in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to communicate with other processing elements for remote data files will be executed successfully. This reliability varies according to (

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

The complexity of the network design pro
The complexity of the network design problem
✍ D. S. Johnson; J. K. Lenstra; A. H. G. Rinnooy Kan πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 278 KB
The bit complexity of the predecessor pr
The bit complexity of the predecessor problem
✍ Y. Afek; M. Cohen; E. Haalman πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 348 KB

A tight bound of 2n -1 bits on the communication complexity of the "predecessor" problem in a synchronous ring (previously known as the "last in a synchronous ring" problem) is presented. @ 1997 Elsevier Science B.V.