---
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@
...