MPI-I-93-107
Expected complexity of graph partitioning problems
Kucera, Ludek
February 1993, 16 pages.
.
Status: available - back from printing
We study one bit broadcast in a one-dimensional network with nodes
${\cal N}_0,\ldots,{\cal N}_n$, in which each ${\cal N}_{i-1}$ sends information to ${\cal N}_i$. We suppose that the broadcasting is synchronous, and at each step each atomic transmission ${\cal N}_{i-1}\rightarrow{\cal N}_i$ could be temporarily incorrect with probability equal to a constant $0
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-107
BibTeX
@TECHREPORT{Kucera93c,
AUTHOR = {Kucera, Ludek},
TITLE = {Expected complexity of graph partitioning problems},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-107},
MONTH = {February},
YEAR = {1993},
ISSN = {0946-011X},
}