---
_id: '64096'
author:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Jinfeng
full_name: Dou, Jinfeng
id: '92888'
last_name: Dou
- first_name: 'Thorsten '
full_name: 'Götte, Thorsten '
last_name: Götte
- first_name: Henning
full_name: Hillebrandt, Henning
id: '74425'
last_name: Hillebrandt
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Scheideler C, Dou J, Götte T, Hillebrandt H, Werthmann J. Distributed and
Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. . In:
; 2025.'
apa: Scheideler, C., Dou, J., Götte, T., Hillebrandt, H., & Werthmann, J. (2025).
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted
Graphs. .
bibtex: '@inproceedings{Scheideler_Dou_Götte_Hillebrandt_Werthmann_2025, place={ITCS
2025: 45:1-45:26}, title={Distributed and Parallel Low-Diameter Decompositions
for Arbitrary and Restricted Graphs. }, author={Scheideler, Christian and Dou,
Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Werthmann, Julian},
year={2025} }'
chicago: 'Scheideler, Christian, Jinfeng Dou, Thorsten Götte, Henning Hillebrandt,
and Julian Werthmann. “Distributed and Parallel Low-Diameter Decompositions for
Arbitrary and Restricted Graphs. .” ITCS 2025: 45:1-45:26, 2025.'
ieee: C. Scheideler, J. Dou, T. Götte, H. Hillebrandt, and J. Werthmann, “Distributed
and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs.
,” 2025.
mla: Scheideler, Christian, et al. Distributed and Parallel Low-Diameter Decompositions
for Arbitrary and Restricted Graphs. . 2025.
short: 'C. Scheideler, J. Dou, T. Götte, H. Hillebrandt, J. Werthmann, in: ITCS
2025: 45:1-45:26, 2025.'
date_created: 2026-02-10T09:10:14Z
date_updated: 2026-02-11T09:11:29Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
language:
- iso: eng
place: 'ITCS 2025: 45:1-45:26'
status: public
title: 'Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted
Graphs. '
type: conference
user_id: '15578'
year: '2025'
...
---
_id: '64095'
author:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: 'John '
full_name: 'Augustine , John '
last_name: 'Augustine '
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Scheideler C, Augustine J, Werthmann J. Supervised Distributed Computing.
. In: ; 2025.'
apa: Scheideler, C., Augustine , J., & Werthmann, J. (2025). Supervised Distributed
Computing. .
bibtex: '@inproceedings{Scheideler_Augustine _Werthmann_2025, place={Euro-Par (3)
2025: 48-62}, title={Supervised Distributed Computing. }, author={Scheideler,
Christian and Augustine , John and Werthmann, Julian}, year={2025} }'
chicago: 'Scheideler, Christian, John Augustine , and Julian Werthmann. “Supervised
Distributed Computing. .” Euro-Par (3) 2025: 48-62, 2025.'
ieee: C. Scheideler, J. Augustine , and J. Werthmann, “Supervised Distributed Computing.
,” 2025.
mla: Scheideler, Christian, et al. Supervised Distributed Computing. . 2025.
short: 'C. Scheideler, J. Augustine , J. Werthmann, in: Euro-Par (3) 2025: 48-62,
2025.'
date_created: 2026-02-10T09:04:56Z
date_updated: 2026-02-11T09:11:35Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
language:
- iso: eng
place: 'Euro-Par (3) 2025: 48-62'
status: public
title: 'Supervised Distributed Computing. '
type: conference
user_id: '15578'
year: '2025'
...
---
_id: '61184'
author:
- first_name: John
full_name: Augustine, John
last_name: Augustine
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Augustine J, Scheideler C, Werthmann J. Supervised Distributed Computing.
In: Lecture Notes in Computer Science. Springer Nature Switzerland; 2025.
doi:10.1007/978-3-031-99872-0_4'
apa: Augustine, J., Scheideler, C., & Werthmann, J. (2025). Supervised Distributed
Computing. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-031-99872-0_4
bibtex: '@inproceedings{Augustine_Scheideler_Werthmann_2025, place={Cham}, title={Supervised
Distributed Computing}, DOI={10.1007/978-3-031-99872-0_4},
booktitle={Lecture Notes in Computer Science}, publisher={Springer Nature Switzerland},
author={Augustine, John and Scheideler, Christian and Werthmann, Julian}, year={2025}
}'
chicago: 'Augustine, John, Christian Scheideler, and Julian Werthmann. “Supervised
Distributed Computing.” In Lecture Notes in Computer Science. Cham: Springer
Nature Switzerland, 2025. https://doi.org/10.1007/978-3-031-99872-0_4.'
ieee: 'J. Augustine, C. Scheideler, and J. Werthmann, “Supervised Distributed Computing,”
2025, doi: 10.1007/978-3-031-99872-0_4.'
mla: Augustine, John, et al. “Supervised Distributed Computing.” Lecture Notes
in Computer Science, Springer Nature Switzerland, 2025, doi:10.1007/978-3-031-99872-0_4.
short: 'J. Augustine, C. Scheideler, J. Werthmann, in: Lecture Notes in Computer
Science, Springer Nature Switzerland, Cham, 2025.'
date_created: 2025-09-11T08:30:57Z
date_updated: 2025-09-11T08:33:27Z
doi: 10.1007/978-3-031-99872-0_4
language:
- iso: eng
place: Cham
publication: Lecture Notes in Computer Science
publication_identifier:
isbn:
- '9783031998713'
- '9783031998720'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
status: public
title: Supervised Distributed Computing
type: conference
user_id: '50024'
year: '2025'
...
---
_id: '59268'
author:
- first_name: Jinfeng
full_name: Dou, Jinfeng
id: '92888'
last_name: Dou
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Henning
full_name: Hillebrandt, Henning
id: '74425'
last_name: Hillebrandt
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Dou J, Götte T, Hillebrandt H, Scheideler C, Werthmann J. Distributed and
Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In:
Meka R, ed. 16th Innovations in Theoretical Computer Science Conference (ITCS
2025). Vol 325. Leibniz International Proceedings in Informatics (LIPIcs).
Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2025:45:1–45:26. doi:10.4230/LIPIcs.ITCS.2025.45'
apa: Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., & Werthmann, J. (2025).
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted
Graphs. In R. Meka (Ed.), 16th Innovations in Theoretical Computer Science
Conference (ITCS 2025) (Vol. 325, p. 45:1–45:26). Schloss Dagstuhl – Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2025.45
bibtex: '@inproceedings{Dou_Götte_Hillebrandt_Scheideler_Werthmann_2025, place={Dagstuhl,
Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)},
title={Distributed and Parallel Low-Diameter Decompositions for Arbitrary and
Restricted Graphs}, volume={325}, DOI={10.4230/LIPIcs.ITCS.2025.45},
booktitle={16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Dou, Jinfeng
and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann,
Julian}, editor={Meka, Raghu}, year={2025}, pages={45:1–45:26}, collection={Leibniz
International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Dou, Jinfeng, Thorsten Götte, Henning Hillebrandt, Christian Scheideler,
and Julian Werthmann. “Distributed and Parallel Low-Diameter Decompositions for
Arbitrary and Restricted Graphs.” In 16th Innovations in Theoretical Computer
Science Conference (ITCS 2025), edited by Raghu Meka, 325:45:1–45:26. Leibniz
International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss
Dagstuhl – Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.45.'
ieee: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, and J. Werthmann, “Distributed
and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs,”
in 16th Innovations in Theoretical Computer Science Conference (ITCS 2025),
2025, vol. 325, p. 45:1–45:26, doi: 10.4230/LIPIcs.ITCS.2025.45.'
mla: Dou, Jinfeng, et al. “Distributed and Parallel Low-Diameter Decompositions
for Arbitrary and Restricted Graphs.” 16th Innovations in Theoretical Computer
Science Conference (ITCS 2025), edited by Raghu Meka, vol. 325, Schloss Dagstuhl
– Leibniz-Zentrum für Informatik, 2025, p. 45:1–45:26, doi:10.4230/LIPIcs.ITCS.2025.45.
short: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, J. Werthmann, in: R. Meka
(Ed.), 16th Innovations in Theoretical Computer Science Conference (ITCS 2025),
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2025, p.
45:1–45:26.'
date_created: 2025-04-02T14:09:19Z
date_updated: 2025-10-15T12:57:11Z
doi: 10.4230/LIPIcs.ITCS.2025.45
editor:
- first_name: Raghu
full_name: Meka, Raghu
last_name: Meka
intvolume: ' 325'
language:
- iso: eng
page: 45:1–45:26
place: Dagstuhl, Germany
publication: 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
publication_identifier:
isbn:
- 978-3-95977-361-4
issn:
- 1868-8969
publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted
Graphs
type: conference
user_id: '34727'
volume: 325
year: '2025'
...
---
_id: '64101'
author:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: 'Sam '
full_name: 'Coy, Sam '
last_name: Coy
- first_name: 'Arthur '
full_name: 'Czumaj, Arthur '
last_name: Czumaj
- first_name: 'Philipp '
full_name: 'Schneider, Philipp '
last_name: Schneider
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Scheideler C, Coy S, Czumaj A, Schneider P, Werthmann J. Routing schemes for
hybrid communication networks. . Routing schemes for hybrid communication networks
Theor Comput Sci 985: 114352 (2024). Published online 2024.'
apa: 'Scheideler, C., Coy, S., Czumaj, A., Schneider, P., & Werthmann, J. (2024).
Routing schemes for hybrid communication networks. . Routing Schemes for Hybrid
Communication Networks. Theor. Comput. Sci. 985: 114352 (2024).'
bibtex: '@article{Scheideler_Coy_Czumaj_Schneider_Werthmann_2024, title={Routing
schemes for hybrid communication networks. }, journal={Routing schemes for hybrid
communication networks. Theor. Comput. Sci. 985: 114352 (2024)}, author={Scheideler,
Christian and Coy, Sam and Czumaj, Arthur and Schneider, Philipp and Werthmann,
Julian}, year={2024} }'
chicago: 'Scheideler, Christian, Sam Coy, Arthur Czumaj, Philipp Schneider, and
Julian Werthmann. “Routing Schemes for Hybrid Communication Networks. .” Routing
Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024),
2024.'
ieee: 'C. Scheideler, S. Coy, A. Czumaj, P. Schneider, and J. Werthmann, “Routing
schemes for hybrid communication networks. ,” Routing schemes for hybrid communication
networks. Theor. Comput. Sci. 985: 114352 (2024), 2024.'
mla: 'Scheideler, Christian, et al. “Routing Schemes for Hybrid Communication Networks.
.” Routing Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985:
114352 (2024), 2024.'
short: 'C. Scheideler, S. Coy, A. Czumaj, P. Schneider, J. Werthmann, Routing Schemes
for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024) (2024).'
date_created: 2026-02-10T10:00:43Z
date_updated: 2026-02-11T09:12:57Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
language:
- iso: eng
publication: 'Routing schemes for hybrid communication networks. Theor. Comput. Sci.
985: 114352 (2024)'
status: public
title: 'Routing schemes for hybrid communication networks. '
type: journal_article
user_id: '15578'
year: '2024'
...
---
_id: '61172'
article_number: '114352'
author:
- first_name: Sam
full_name: Coy, Sam
last_name: Coy
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Philipp
full_name: Schneider, Philipp
last_name: Schneider
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: Coy S, Czumaj A, Scheideler C, Schneider P, Werthmann J. Routing Schemes for
Hybrid Communication Networks. Theoretical Computer Science. 2024;985.
doi:10.1016/j.tcs.2023.114352
apa: Coy, S., Czumaj, A., Scheideler, C., Schneider, P., & Werthmann, J. (2024).
Routing Schemes for Hybrid Communication Networks. Theoretical Computer Science,
985, Article 114352. https://doi.org/10.1016/j.tcs.2023.114352
bibtex: '@article{Coy_Czumaj_Scheideler_Schneider_Werthmann_2024, title={Routing
Schemes for Hybrid Communication Networks}, volume={985}, DOI={10.1016/j.tcs.2023.114352},
number={114352}, journal={Theoretical Computer Science}, publisher={Elsevier BV},
author={Coy, Sam and Czumaj, Artur and Scheideler, Christian and Schneider, Philipp
and Werthmann, Julian}, year={2024} }'
chicago: Coy, Sam, Artur Czumaj, Christian Scheideler, Philipp Schneider, and Julian
Werthmann. “Routing Schemes for Hybrid Communication Networks.” Theoretical
Computer Science 985 (2024). https://doi.org/10.1016/j.tcs.2023.114352.
ieee: 'S. Coy, A. Czumaj, C. Scheideler, P. Schneider, and J. Werthmann, “Routing
Schemes for Hybrid Communication Networks,” Theoretical Computer Science,
vol. 985, Art. no. 114352, 2024, doi: 10.1016/j.tcs.2023.114352.'
mla: Coy, Sam, et al. “Routing Schemes for Hybrid Communication Networks.” Theoretical
Computer Science, vol. 985, 114352, Elsevier BV, 2024, doi:10.1016/j.tcs.2023.114352.
short: S. Coy, A. Czumaj, C. Scheideler, P. Schneider, J. Werthmann, Theoretical
Computer Science 985 (2024).
date_created: 2025-09-10T14:26:11Z
date_updated: 2025-09-10T14:52:21Z
department:
- _id: '79'
doi: 10.1016/j.tcs.2023.114352
intvolume: ' 985'
language:
- iso: eng
project:
- _id: '5'
name: 'SFB 901; TP A1: Möglichkeiten und Grenzen lokaler Strategien in dynamischen
Netzen'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier BV
status: public
title: Routing Schemes for Hybrid Communication Networks
type: journal_article
user_id: '50024'
volume: 985
year: '2024'
...
---
_id: '43109'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Christina
full_name: Kolb, Christina
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Kolb C, Scheideler C, Werthmann J. Beep-and-Sleep: Message and Energy
Efficient Set Cover. Theor Comput Sci. 2023;950:113756. doi:10.1016/j.tcs.2023.113756'
apa: 'Götte, T., Kolb, C., Scheideler, C., & Werthmann, J. (2023). Beep-and-Sleep:
Message and Energy Efficient Set Cover. Theor. Comput. Sci., 950,
113756. https://doi.org/10.1016/j.tcs.2023.113756'
bibtex: '@article{Götte_Kolb_Scheideler_Werthmann_2023, title={Beep-and-Sleep: Message
and Energy Efficient Set Cover}, volume={950}, DOI={10.1016/j.tcs.2023.113756},
journal={Theor. Comput. Sci.}, author={Götte, Thorsten and Kolb, Christina and
Scheideler, Christian and Werthmann, Julian}, year={2023}, pages={113756} }'
chicago: 'Götte, Thorsten, Christina Kolb, Christian Scheideler, and Julian Werthmann.
“Beep-and-Sleep: Message and Energy Efficient Set Cover.” Theor. Comput. Sci.
950 (2023): 113756. https://doi.org/10.1016/j.tcs.2023.113756.'
ieee: 'T. Götte, C. Kolb, C. Scheideler, and J. Werthmann, “Beep-and-Sleep: Message
and Energy Efficient Set Cover,” Theor. Comput. Sci., vol. 950, p. 113756,
2023, doi: 10.1016/j.tcs.2023.113756.'
mla: 'Götte, Thorsten, et al. “Beep-and-Sleep: Message and Energy Efficient Set
Cover.” Theor. Comput. Sci., vol. 950, 2023, p. 113756, doi:10.1016/j.tcs.2023.113756.'
short: T. Götte, C. Kolb, C. Scheideler, J. Werthmann, Theor. Comput. Sci. 950 (2023)
113756.
date_created: 2023-03-27T07:45:44Z
date_updated: 2023-03-27T09:55:04Z
department:
- _id: '79'
doi: 10.1016/j.tcs.2023.113756
intvolume: ' 950'
language:
- iso: eng
page: '113756'
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Theor. Comput. Sci.
status: public
title: 'Beep-and-Sleep: Message and Energy Efficient Set Cover'
type: journal_article
user_id: '15504'
volume: 950
year: '2023'
...
---
_id: '45188'
author:
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Sam
full_name: Coy, Sam
last_name: Coy
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Philipp
full_name: Schneider, Philipp
last_name: Schneider
citation:
ama: 'Werthmann J, Scheideler C, Coy S, Czumaj A, Schneider P. Routing Schemes for
Hybrid Communication Networks. In: ; 2023. doi:10.48550/ARXIV.2210.05333'
apa: Werthmann, J., Scheideler, C., Coy, S., Czumaj, A., & Schneider, P. (2023).
Routing Schemes for Hybrid Communication Networks. https://doi.org/10.48550/ARXIV.2210.05333
bibtex: '@inproceedings{Werthmann_Scheideler_Coy_Czumaj_Schneider_2023, title={Routing
Schemes for Hybrid Communication Networks}, DOI={10.48550/ARXIV.2210.05333},
author={Werthmann, Julian and Scheideler, Christian and Coy, Sam and Czumaj, Artur
and Schneider, Philipp}, year={2023} }'
chicago: Werthmann, Julian, Christian Scheideler, Sam Coy, Artur Czumaj, and Philipp
Schneider. “Routing Schemes for Hybrid Communication Networks,” 2023. https://doi.org/10.48550/ARXIV.2210.05333.
ieee: 'J. Werthmann, C. Scheideler, S. Coy, A. Czumaj, and P. Schneider, “Routing
Schemes for Hybrid Communication Networks,” 2023, doi: 10.48550/ARXIV.2210.05333.'
mla: Werthmann, Julian, et al. Routing Schemes for Hybrid Communication Networks.
2023, doi:10.48550/ARXIV.2210.05333.
short: 'J. Werthmann, C. Scheideler, S. Coy, A. Czumaj, P. Schneider, in: 2023.'
date_created: 2023-05-22T09:17:50Z
date_updated: 2023-05-22T09:37:25Z
department:
- _id: '79'
doi: 10.48550/ARXIV.2210.05333
language:
- iso: eng
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
status: public
title: Routing Schemes for Hybrid Communication Networks
type: conference
user_id: '50024'
year: '2023'
...
---
_id: '45192'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Kristian
full_name: Hinnenthal, Kristian
id: '32229'
last_name: Hinnenthal
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction
of Overlays. Distributed Computing. Published online 2023. doi:https://doi.org/10.1007/s00446-023-00442-4
apa: Götte, T., Hinnenthal, K., Scheideler, C., & Werthmann, J. (2023). Time-Optimal
Construction of Overlays. Distributed Computing. https://doi.org/10.1007/s00446-023-00442-4
bibtex: '@article{Götte_Hinnenthal_Scheideler_Werthmann_2023, title={Time-Optimal
Construction of Overlays}, DOI={https://doi.org/10.1007/s00446-023-00442-4},
journal={Distributed Computing}, author={Götte, Thorsten and Hinnenthal, Kristian
and Scheideler, Christian and Werthmann, Julian}, year={2023} }'
chicago: Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian
Werthmann. “Time-Optimal Construction of Overlays.” Distributed Computing,
2023. https://doi.org/10.1007/s00446-023-00442-4.
ieee: 'T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction
of Overlays,” Distributed Computing, 2023, doi: https://doi.org/10.1007/s00446-023-00442-4.'
mla: Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” Distributed
Computing, 2023, doi:https://doi.org/10.1007/s00446-023-00442-4.
short: T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, Distributed Computing
(2023).
date_created: 2023-05-22T14:34:34Z
date_updated: 2023-05-23T12:38:57Z
doi: https://doi.org/10.1007/s00446-023-00442-4
language:
- iso: eng
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '13'
name: 'SFB 901 - C1: SFB 901 - Subproject C1'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Distributed Computing
status: public
title: Time-Optimal Construction of Overlays
type: journal_article
user_id: '477'
year: '2023'
...
---
_id: '45875'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Knollmann T, Meyer auf der Heide F, Scheideler C, Werthmann J. Capabilities
and Limitations of Local Strategies in Dynamic Networks. In: Haake C-J, Meyer
auf der Heide F, Platzner M, Wachsmuth H, Wehrheim H, eds. On-The-Fly Computing
-- Individualized IT-Services in Dynamic Markets. Vol 412. Verlagsschriftenreihe
des Heinz Nixdorf Instituts. Heinz Nixdorf Institut, Universität Paderborn; 2023:1--20.
doi:10.5281/zenodo.8060372'
apa: Götte, T., Knollmann, T., Meyer auf der Heide, F., Scheideler, C., & Werthmann,
J. (2023). Capabilities and Limitations of Local Strategies in Dynamic Networks.
In C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, & H. Wehrheim
(Eds.), On-The-Fly Computing -- Individualized IT-services in dynamic markets
(Vol. 412, pp. 1--20). Heinz Nixdorf Institut, Universität Paderborn. https://doi.org/10.5281/zenodo.8060372
bibtex: '@inbook{Götte_Knollmann_Meyer auf der Heide_Scheideler_Werthmann_2023,
place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts},
title={Capabilities and Limitations of Local Strategies in Dynamic Networks},
volume={412}, DOI={10.5281/zenodo.8060372},
booktitle={On-The-Fly Computing -- Individualized IT-services in dynamic markets},
publisher={Heinz Nixdorf Institut, Universität Paderborn}, author={Götte, Thorsten
and Knollmann, Till and Meyer auf der Heide, Friedhelm and Scheideler, Christian
and Werthmann, Julian}, editor={Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm
and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}, year={2023},
pages={1--20}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts}
}'
chicago: 'Götte, Thorsten, Till Knollmann, Friedhelm Meyer auf der Heide, Christian
Scheideler, and Julian Werthmann. “Capabilities and Limitations of Local Strategies
in Dynamic Networks.” In On-The-Fly Computing -- Individualized IT-Services
in Dynamic Markets, edited by Claus-Jochen Haake, Friedhelm Meyer auf der
Heide, Marco Platzner, Henning Wachsmuth, and Heike Wehrheim, 412:1--20. Verlagsschriftenreihe
Des Heinz Nixdorf Instituts. Paderborn: Heinz Nixdorf Institut, Universität Paderborn,
2023. https://doi.org/10.5281/zenodo.8060372.'
ieee: 'T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, and J. Werthmann,
“Capabilities and Limitations of Local Strategies in Dynamic Networks,” in On-The-Fly
Computing -- Individualized IT-services in dynamic markets, vol. 412, C.-J.
Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, and H. Wehrheim, Eds.
Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023, pp. 1--20.'
mla: Götte, Thorsten, et al. “Capabilities and Limitations of Local Strategies in
Dynamic Networks.” On-The-Fly Computing -- Individualized IT-Services in Dynamic
Markets, edited by Claus-Jochen Haake et al., vol. 412, Heinz Nixdorf Institut,
Universität Paderborn, 2023, pp. 1--20, doi:10.5281/zenodo.8060372.
short: 'T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, J. Werthmann,
in: C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim
(Eds.), On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets,
Heinz Nixdorf Institut, Universität Paderborn, Paderborn, 2023, pp. 1--20.'
date_created: 2023-07-07T06:21:38Z
date_updated: 2023-07-07T06:21:57Z
ddc:
- '004'
department:
- _id: '7'
doi: 10.5281/zenodo.8060372
editor:
- first_name: Claus-Jochen
full_name: Haake, Claus-Jochen
last_name: Haake
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
last_name: Meyer auf der Heide
- first_name: Marco
full_name: Platzner, Marco
last_name: Platzner
- first_name: Henning
full_name: Wachsmuth, Henning
last_name: Wachsmuth
- first_name: Heike
full_name: Wehrheim, Heike
last_name: Wehrheim
file:
- access_level: open_access
content_type: application/pdf
creator: ups
date_created: 2023-07-07T06:20:43Z
date_updated: 2023-07-07T06:20:43Z
file_id: '45876'
file_name: A1-Chapter-SFB-Buch-Final.pdf
file_size: 543715
relation: main_file
file_date_updated: 2023-07-07T06:20:43Z
has_accepted_license: '1'
intvolume: ' 412'
language:
- iso: eng
oa: '1'
page: 1--20
place: Paderborn
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
grant_number: '160364472'
name: 'SFB 901 - A1: SFB 901 - Möglichkeiten und Grenzen lokaler Strategien in dynamischen
Netzen (Subproject A1)'
publication: On-The-Fly Computing -- Individualized IT-services in dynamic markets
publisher: Heinz Nixdorf Institut, Universität Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: Capabilities and Limitations of Local Strategies in Dynamic Networks
type: book_chapter
user_id: '477'
volume: 412
year: '2023'
...
---
_id: '45193'
author:
- first_name: Jinfeng
full_name: Dou, Jinfeng
id: '92888'
last_name: Dou
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Henning
full_name: Hillebrandt, Henning
id: '74425'
last_name: Hillebrandt
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Dou J, Götte T, Hillebrandt H, Scheideler C, Werthmann J. Brief Announcement:
Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs.
In: Proc. of the 42nd ACM Symposium on Principles of Distributed Computing
(PODC ’23). ; 2023.'
apa: 'Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., & Werthmann, J. (2023).
Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs. Proc. of the 42nd ACM Symposium on Principles of Distributed
Computing (PODC ’23). ACM Symposium on Principles of Distributed Computing
(PODC), Orlando, USA.'
bibtex: '@inproceedings{Dou_Götte_Hillebrandt_Scheideler_Werthmann_2023, title={Brief
Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs}, booktitle={Proc. of the 42nd ACM Symposium on Principles of
Distributed Computing (PODC ’23)}, author={Dou, Jinfeng and Götte, Thorsten and
Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}, year={2023}
}'
chicago: 'Dou, Jinfeng, Thorsten Götte, Henning Hillebrandt, Christian Scheideler,
and Julian Werthmann. “Brief Announcement: Distributed Construction of Near-Optimal
Compact Routing Schemes for Planar Graphs.” In Proc. of the 42nd ACM Symposium
on Principles of Distributed Computing (PODC ’23), 2023.'
ieee: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, and J. Werthmann, “Brief
Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs,” presented at the ACM Symposium on Principles of Distributed
Computing (PODC), Orlando, USA, 2023.'
mla: 'Dou, Jinfeng, et al. “Brief Announcement: Distributed Construction of Near-Optimal
Compact Routing Schemes for Planar Graphs.” Proc. of the 42nd ACM Symposium
on Principles of Distributed Computing (PODC ’23), 2023.'
short: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, J. Werthmann, in: Proc.
of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23), 2023.'
conference:
end_date: 2023-06-25
location: Orlando, USA
name: ACM Symposium on Principles of Distributed Computing (PODC)
start_date: 2023-06-19
date_created: 2023-05-22T14:42:31Z
date_updated: 2025-10-15T12:57:48Z
language:
- iso: eng
project:
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
- _id: '1'
name: 'SFB 901: SFB 901'
publication: Proc. of the 42nd ACM Symposium on Principles of Distributed Computing
(PODC '23)
status: public
title: 'Brief Announcement: Distributed Construction of Near-Optimal Compact Routing
Schemes for Planar Graphs'
type: conference
user_id: '34727'
year: '2023'
...
---
_id: '21084'
author:
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: Werthmann J. Derandomization and Local Graph Problems in the Node-Capacitated
Clique.; 2021.
apa: Werthmann, J. (2021). Derandomization and Local Graph Problems in the Node-Capacitated
Clique.
bibtex: '@book{Werthmann_2021, title={Derandomization and Local Graph Problems in
the Node-Capacitated Clique}, author={Werthmann, Julian}, year={2021} }'
chicago: Werthmann, Julian. Derandomization and Local Graph Problems in the Node-Capacitated
Clique, 2021.
ieee: J. Werthmann, Derandomization and Local Graph Problems in the Node-Capacitated
Clique. 2021.
mla: Werthmann, Julian. Derandomization and Local Graph Problems in the Node-Capacitated
Clique. 2021.
short: J. Werthmann, Derandomization and Local Graph Problems in the Node-Capacitated
Clique, 2021.
date_created: 2021-01-26T13:58:14Z
date_updated: 2022-01-06T06:54:44Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
title: Derandomization and Local Graph Problems in the Node-Capacitated Clique
type: mastersthesis
user_id: '15504'
year: '2021'
...
---
_id: '22283'
abstract:
- lang: eng
text: " 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$."
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Kristian
full_name: Hinnenthal, Kristian
id: '32229'
last_name: Hinnenthal
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction
of Overlays. In: Censor-Hillel K, ed. Proc. of the 40th ACM Symposium on Principles
of Distributed Computing (PODC ’21). New York: ACM. doi:10.1145/3465084.3467932'
apa: 'Götte, T., Hinnenthal, K., Scheideler, C., & Werthmann, J. (n.d.). Time-Optimal
Construction of Overlays. In K. Censor-Hillel (Ed.), Proc. of the 40th ACM
Symposium on Principles of Distributed Computing (PODC ’21). New York: ACM.
https://doi.org/10.1145/3465084.3467932'
bibtex: '@inproceedings{Götte_Hinnenthal_Scheideler_Werthmann, place={New York},
title={Time-Optimal Construction of Overlays}, DOI={10.1145/3465084.3467932},
booktitle={Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC ’21)}, publisher={ACM}, author={Götte, Thorsten and Hinnenthal, Kristian
and Scheideler, Christian and Werthmann, Julian}, editor={Censor-Hillel, KerenEditor}
}'
chicago: 'Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian
Werthmann. “Time-Optimal Construction of Overlays.” In Proc. of the 40th ACM
Symposium on Principles of Distributed Computing (PODC ’21), edited by Keren
Censor-Hillel. New York: ACM, n.d. https://doi.org/10.1145/3465084.3467932.'
ieee: T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction
of Overlays,” in Proc. of the 40th ACM Symposium on Principles of Distributed
Computing (PODC ’21), Virtual.
mla: Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” Proc. of
the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21),
edited by Keren Censor-Hillel, ACM, doi:10.1145/3465084.3467932.
short: 'T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, in: K. Censor-Hillel
(Ed.), Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC ’21), ACM, New York, n.d.'
conference:
end_date: 2021-07-30
location: Virtual
name: ACM Symposium on Principles of Distributed Computing (PODC)
start_date: 2021-07-26
date_created: 2021-06-06T19:10:26Z
date_updated: 2022-01-06T06:55:30Z
ddc:
- '000'
department:
- _id: '34'
doi: 10.1145/3465084.3467932
editor:
- first_name: Keren
full_name: Censor-Hillel, Keren
last_name: Censor-Hillel
file:
- access_level: closed
content_type: application/pdf
creator: thgoette
date_created: 2021-06-06T19:12:49Z
date_updated: 2021-06-06T19:12:49Z
file_id: '22284'
file_name: Wicked_Fast_Overlay_Construction(1).pdf
file_size: 590875
relation: main_file
success: 1
file_date_updated: 2021-06-06T19:12:49Z
has_accepted_license: '1'
language:
- iso: eng
place: New York
project:
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '4'
name: SFB 901 - Project Area C
- _id: '13'
name: SFB 901 - Subproject C1
- _id: '1'
name: SFB 901
publication: Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC '21)
publication_status: accepted
publisher: ACM
status: public
title: Time-Optimal Construction of Overlays
type: conference
user_id: '477'
year: '2021'
...
---
_id: '26888'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Christina
full_name: Kolb, Christina
id: '43647'
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Kolb C, Scheideler C, Werthmann J. Beep-And-Sleep: Message and Energy
Efficient Set Cover. In: Algorithms for Sensor Systems (ALGOSENSORS ’21).
; 2021. doi:10.1007/978-3-030-89240-1_7'
apa: 'Götte, T., Kolb, C., Scheideler, C., & Werthmann, J. (2021). Beep-And-Sleep:
Message and Energy Efficient Set Cover. In Algorithms for Sensor Systems (ALGOSENSORS
’21). ALGOSENSORS 2021, Lisbon, Portgual. https://doi.org/10.1007/978-3-030-89240-1_7'
bibtex: '@inbook{Götte_Kolb_Scheideler_Werthmann_2021, place={Cham}, title={Beep-And-Sleep:
Message and Energy Efficient Set Cover}, DOI={10.1007/978-3-030-89240-1_7},
booktitle={Algorithms for Sensor Systems (ALGOSENSORS ’21)}, author={Götte, Thorsten
and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}, year={2021}
}'
chicago: 'Götte, Thorsten, Christina Kolb, Christian Scheideler, and Julian Werthmann.
“Beep-And-Sleep: Message and Energy Efficient Set Cover.” In Algorithms for
Sensor Systems (ALGOSENSORS ’21). Cham, 2021. https://doi.org/10.1007/978-3-030-89240-1_7.'
ieee: 'T. Götte, C. Kolb, C. Scheideler, and J. Werthmann, “Beep-And-Sleep: Message
and Energy Efficient Set Cover,” in Algorithms for Sensor Systems (ALGOSENSORS
’21), Cham, 2021.'
mla: 'Götte, Thorsten, et al. “Beep-And-Sleep: Message and Energy Efficient Set
Cover.” Algorithms for Sensor Systems (ALGOSENSORS ’21), 2021, doi:10.1007/978-3-030-89240-1_7.'
short: 'T. Götte, C. Kolb, C. Scheideler, J. Werthmann, in: Algorithms for Sensor
Systems (ALGOSENSORS ’21), Cham, 2021.'
conference:
location: Lisbon, Portgual
name: ALGOSENSORS 2021
date_created: 2021-10-26T12:06:04Z
date_updated: 2022-11-18T10:01:36Z
doi: 10.1007/978-3-030-89240-1_7
language:
- iso: eng
place: Cham
project:
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '1'
name: 'SFB 901: SFB 901'
publication: Algorithms for Sensor Systems (ALGOSENSORS '21)
publication_identifier:
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: 'Beep-And-Sleep: Message and Energy Efficient Set Cover'
type: book_chapter
user_id: '477'
year: '2021'
...