MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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:

Hide details for BibTeXBibTeX
  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},