de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Broadcasting through a noisy one-dimensional network

MPG-Autoren

Kucera,  Ludek
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-106.pdf
(beliebiger Volltext), 12MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kucera, L.(1993). Broadcasting through a noisy one-dimensional network (MPI-I-93-106). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B73D-6
Zusammenfassung
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.