---
res:
  bibo_abstract:
  - "    We show how to construct an overlay network of constant degree and diameter
    $O(\\log n)$ in time $O(\\log n)$ starting from an arbitrary weakly connected
    graph.\r\n    We assume a synchronous communication network in which nodes can
    send messages to nodes they know the identifier of and establish new connections
    by sending node identifiers.\r\n    If the initial network's graph is weakly connected
    and has constant degree, then our algorithm constructs the desired topology with
    each node sending and receiving only $O(\\log n)$ messages in each round in time
    $O(\\log n)$, w.h.p., which beats the currently best $O(\\log^{3/2} n)$ time algorithm
    of [Götte et al., SIROCCO'19].\r\n    Since the problem cannot be solved faster
    than by using pointer jumping for $O(\\log n)$ rounds (which would even require
    each node to communicate $\\Omega(n)$ bits), our algorithm is asymptotically optimal.\r\n
    \   We achieve this speedup by using short random walks to repeatedly establish
    random connections between the nodes that quickly reduce the conductance of the
    graph using an observation of [Kwok and Lau, APPROX'14].\r\n    \r\n    Additionally,
    we show how our algorithm can be used to efficiently solve graph problems in \\emph{hybrid
    networks} [Augustine et al., SODA'20].\r\n    Motivated by the idea that nodes
    possess two different modes of communication, we assume that communication of
    the \\emph{initial} edges is unrestricted. In contrast, only polylogarithmically
    many messages can be communicated over edges that have been established throughout
    an algorithm's execution.\r\n    For an (undirected) graph $G$ with arbitrary
    degree, we show how to compute connected components, a spanning tree, and biconnected
    components in time $O(\\log n)$, w.h.p.\r\n    Furthermore, we show how to compute
    an MIS in time $O(\\log d + \\log \\log n)$, w.h.p., where $d$ is the initial
    degree of $G$.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Thorsten
      foaf_name: Götte, Thorsten
      foaf_surname: Götte
      foaf_workInfoHomepage: http://www.librecat.org/personId=34727
  - foaf_Person:
      foaf_givenName: Kristian
      foaf_name: Hinnenthal, Kristian
      foaf_surname: Hinnenthal
      foaf_workInfoHomepage: http://www.librecat.org/personId=32229
  - foaf_Person:
      foaf_givenName: Christian
      foaf_name: Scheideler, Christian
      foaf_surname: Scheideler
      foaf_workInfoHomepage: http://www.librecat.org/personId=20792
  - foaf_Person:
      foaf_givenName: Julian
      foaf_name: Werthmann, Julian
      foaf_surname: Werthmann
      foaf_workInfoHomepage: http://www.librecat.org/personId=50024
  bibo_doi: 10.1145/3465084.3467932
  dct_date: 2021^xs_gYear
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Time-Optimal Construction of Overlays@
...