# MPI-I-93-106

## Broadcasting through a noisy one-dimensional network

### Kucera, Ludek

**MPI-I-93-106**. February** **1993, 14 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We study the expected time complexity of two graph partitioning

problems: the graph coloring and the cut into equal parts.

If $k=o(\sqrt{n/\log n})$, we can test whether two vertices of a $k$-colorable

graph can be $k$-colored by the same color in time $O(k\log n)$ per pair of

vertices with

$O(k^4\log^3n)$-time preprocessing in such a way that for almost all $k$-colorable

graphs the answer is correct for all pairs of vertices.

As a consequence, we obtain a sublinear (with respect to the number of edges)

expected time algorithm for $k$-coloring

of $k$-colorable graphs (assuming the uniform input distribution).

Similarly, if $ c\le (1/8-\epsilon)n^2 $, $ \epsilon>0 $ a constant,

and $G$ is a graph having cut of the vertex

set into two equal parts with at most $c$ cross-edges, we can test whether two

vertices belong to the same class of some $c$-cut in time $O(\log n)$ per vertex

with $O(\log^3n)$-time preprocessing in such a way that for almost all graphs

having a $c$-cut the answer is correct for all pairs of vertices.

The methods presented in the paper can also be used to other graph partitioning

problems, e.g. the largest clique or independent subset.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-106.pdf | 12184 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-106

**BibTeX**
`@TECHREPORT{``Kucera93a``,`

` AUTHOR = {Kucera, Ludek},`

` TITLE = {Broadcasting through a noisy one-dimensional network},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-106},`

` MONTH = {February},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`