Search Results

Documents authored by Steger, Angelika

Document
DOI: 10.4230/LIPIcs.ITCS.2021.60
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability

Authors: Rajko Nenadov, Angelika Steger, and Pascal Su

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.
Cite as

Rajko Nenadov, Angelika Steger, and Pascal Su. An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nenadov_et_al:LIPIcs.ITCS.2021.60,
  author =	{Nenadov, Rajko and Steger, Angelika and Su, Pascal},
  title =	{{An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.60},
  URN =		{urn:nbn:de:0030-drops-135997},
  doi =		{10.4230/LIPIcs.ITCS.2021.60},
  annote =	{Keywords: Random Graphs, Hamilton Cycle, Perfect Matching, Linear Time, Sublinear Algorithm, Random Walk, Coupon Collector}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.17
An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors: Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].
Cite as

Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.ESA.2020.17,
  author =	{Bertschinger, Daniel and Lengler, Johannes and Martinsson, Anders and Meier, Robert and Steger, Angelika and Truji\'{c}, Milo\v{s} and Welzl, Emo},
  title =	{{An Optimal Decentralized (\Delta + 1)-Coloring Algorithm}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.17},
  URN =		{urn:nbn:de:0030-drops-128837},
  doi =		{10.4230/LIPIcs.ESA.2020.17},
  annote =	{Keywords: Decentralized Algorithm, Distributed Computing, Graph Coloring, Randomized Algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.58
The Maximum Label Propagation Algorithm on Sparse Random Graphs

Authors: Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.
Cite as

Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger. The Maximum Label Propagation Algorithm on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knierim_et_al:LIPIcs.APPROX-RANDOM.2019.58,
  author =	{Knierim, Charlotte and Lengler, Johannes and Pfister, Pascal and Schaller, Ulysse and Steger, Angelika},
  title =	{{The Maximum Label Propagation Algorithm on Sparse Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.58},
  URN =		{urn:nbn:de:0030-drops-112731},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.58},
  annote =	{Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact