Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Mütze, Torsten Rast, Thomas Spöhel, Reto dblp dblp dblp Not MPG Author(s): Mütze, Torsten Rast, Thomas
 Editor(s): Randall, Dana dblp Not MPII Editor(s): Randall, Dana
 BibTeX cite key*: Spoehel2011

 Title, Booktitle
 Title*: Coloring random graphs online without creating monochromatic subgraphs Booktitle*: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da11/ URL for downloading the paper: http://www.siam.org/proceedings/soda/2011/SODA11_013_muetzet.pdf Event Address*: San Francisco, CA Language: English Event Date* (no longer used): Organization: Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM) Event Start Date: 23 January 2011 Event End Date: 25 January 2011

 Publisher

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: January Pages: 145-158 Year*: 2011 VG Wort Pages: 40 ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) Abstract: Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph~$G$ is \emph{valid} \wrt some given graph~$F$ if there is no copy of $F$ in $G$ whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph~$\Gnp$ on~$n$ vertices with edge probability~$p=p(n)$ in the following online setting: the vertices of an initially hidden instance of $\Gnp$ are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of $r$ available colors. It is known that for any fixed graph $F$ and any fixed integer $r\geq 2$ this problem has a threshold $p_0(F,r,n)$ in the following sense: For any function $p(n) = o(p_0)$ there is a strategy that \aas (asymptotically almost surely, i.e., with probability tending to 1 as $n$ tends to infinity) finds an $r$-coloring of $\Gnp$ that is valid \wrt $F$ online, and for any function~$p(n)=\omega(p_0)$ \emph{any} online strategy will \aas fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any $F$ and $r$, a value $\gamma=\gamma(F,r)$ such that the threshold of the probabilistic problem is given by $p_0(F,r,n)=n^{-\gamma}$. Our approach yields polynomial-time coloring algorithms that \aas find valid colorings of $\Gnp$ online in the entire regime below the respective thresholds, i.e., for any $p(n) = o(n^{-\gamma})$. Keywords: random graph, graph coloring, online algorithm, average-case analysis Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Spoehel2011,
AUTHOR = {M{\"u}tze, Torsten and Rast, Thomas and Sp{\"o}hel, Reto},
EDITOR = {Randall, Dana},
TITLE = {Coloring random graphs online without creating monochromatic subgraphs},
BOOKTITLE = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)},
PUBLISHER = {SIAM},
YEAR = {2011},
ORGANIZATION = {Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {145--158},