[{"status":"public","date_created":"2023-05-22T14:34:34Z","project":[{"_id":"1","name":"SFB 901: SFB 901"},{"name":"SFB 901 - A: SFB 901 - Project Area A","_id":"2"},{"_id":"4","name":"SFB 901 - C: SFB 901 - Project Area C"},{"name":"SFB 901 - C1: SFB 901 - Subproject C1","_id":"13"},{"name":"SFB 901 - A1: SFB 901 - Subproject A1","_id":"5"}],"author":[{"first_name":"Thorsten","full_name":"Götte, Thorsten","last_name":"Götte","id":"34727"},{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"},{"first_name":"Christian","full_name":"Scheideler, Christian","last_name":"Scheideler","id":"20792"},{"first_name":"Julian","full_name":"Werthmann, Julian","last_name":"Werthmann","id":"50024"}],"publication":"Distributed Computing","user_id":"477","title":"Time-Optimal Construction of Overlays","language":[{"iso":"eng"}],"citation":{"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.","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} }","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).","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."},"type":"journal_article","year":"2023","doi":"https://doi.org/10.1007/s00446-023-00442-4","_id":"45192","date_updated":"2023-05-23T12:38:57Z"},{"doi":"10.17619/UNIPB/1-1169 ","_id":"24887","date_updated":"2022-01-06T06:56:40Z","language":[{"iso":"eng"}],"supervisor":[{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"}],"citation":{"ieee":"K. Hinnenthal, Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter. 2021.","short":"K. Hinnenthal, Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter, 2021.","bibtex":"@book{Hinnenthal_2021, title={Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter}, DOI={10.17619/UNIPB/1-1169 }, author={Hinnenthal, Kristian}, year={2021} }","mla":"Hinnenthal, Kristian. Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter. 2021, doi:10.17619/UNIPB/1-1169 .","ama":"Hinnenthal K. Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter.; 2021. doi:10.17619/UNIPB/1-1169 ","apa":"Hinnenthal, K. (2021). Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter. https://doi.org/10.17619/UNIPB/1-1169 ","chicago":"Hinnenthal, Kristian. Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter, 2021. https://doi.org/10.17619/UNIPB/1-1169 ."},"type":"dissertation","year":"2021","user_id":"15504","title":"Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter","status":"public","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"date_created":"2021-09-22T12:33:44Z","author":[{"first_name":"Kristian","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal","id":"32229"}],"department":[{"_id":"79"}]},{"language":[{"iso":"eng"}],"doi":"10.1145/3465084.3467932","date_updated":"2022-01-06T06:55:30Z","project":[{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"name":"SFB 901 - Project Area C","_id":"4"},{"_id":"13","name":"SFB 901 - Subproject C1"},{"name":"SFB 901","_id":"1"}],"editor":[{"first_name":"Keren","full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel"}],"publication_status":"accepted","department":[{"_id":"34"}],"title":"Time-Optimal Construction of Overlays","place":"New York","year":"2021","citation":{"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.","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.","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","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.","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.","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} }"},"type":"conference","_id":"22283","conference":{"name":"ACM Symposium on Principles of Distributed Computing (PODC)","start_date":"2021-07-26","location":"Virtual","end_date":"2021-07-30"},"status":"public","has_accepted_license":"1","date_created":"2021-06-06T19:10:26Z","file":[{"file_size":590875,"file_id":"22284","creator":"thgoette","content_type":"application/pdf","date_updated":"2021-06-06T19:12:49Z","success":1,"relation":"main_file","date_created":"2021-06-06T19:12:49Z","file_name":"Wicked_Fast_Overlay_Construction(1).pdf","access_level":"closed"}],"publisher":"ACM","author":[{"first_name":"Thorsten","full_name":"Götte, Thorsten","last_name":"Götte","id":"34727"},{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"},{"first_name":"Christian","full_name":"Scheideler, Christian","last_name":"Scheideler","id":"20792"},{"full_name":"Werthmann, Julian","first_name":"Julian","id":"50024","last_name":"Werthmann"}],"publication":"Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)","file_date_updated":"2021-06-06T19:12:49Z","user_id":"477","ddc":["000"],"abstract":[{"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$.","lang":"eng"}]},{"user_id":"15504","title":"Shortest Paths in a Hybrid Network Model","author":[{"full_name":"Augustine, John","first_name":"John","last_name":"Augustine"},{"last_name":"Hinnenthal","id":"32229","first_name":"Kristian","full_name":"Hinnenthal, Kristian"},{"first_name":"Fabian","full_name":"Kuhn, Fabian","last_name":"Kuhn"},{"last_name":"Scheideler","id":"20792","first_name":"Christian","full_name":"Scheideler, Christian"},{"first_name":"Philipp","full_name":"Schneider, Philipp","last_name":"Schneider"}],"publisher":"SIAM","publication":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020","status":"public","date_created":"2021-11-02T10:01:42Z","editor":[{"full_name":"Chawla, Shuchi","first_name":"Shuchi","last_name":"Chawla"}],"date_updated":"2022-01-06T06:57:33Z","_id":"27051","doi":"10.1137/1.9781611975994.78","language":[{"iso":"eng"}],"year":"2020","citation":{"mla":"Augustine, John, et al. “Shortest Paths in a Hybrid Network Model.” Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, edited by Shuchi Chawla, SIAM, 2020, pp. 1280–99, doi:10.1137/1.9781611975994.78.","bibtex":"@inproceedings{Augustine_Hinnenthal_Kuhn_Scheideler_Schneider_2020, title={Shortest Paths in a Hybrid Network Model}, DOI={10.1137/1.9781611975994.78}, booktitle={Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020}, publisher={SIAM}, author={Augustine, John and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp}, editor={Chawla, Shuchi}, year={2020}, pages={1280–1299} }","ama":"Augustine J, Hinnenthal K, Kuhn F, Scheideler C, Schneider P. Shortest Paths in a Hybrid Network Model. In: Chawla S, ed. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. SIAM; 2020:1280-1299. doi:10.1137/1.9781611975994.78","apa":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., & Schneider, P. (2020). Shortest Paths in a Hybrid Network Model. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 (pp. 1280–1299). SIAM. https://doi.org/10.1137/1.9781611975994.78","chicago":"Augustine, John, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. “Shortest Paths in a Hybrid Network Model.” In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, edited by Shuchi Chawla, 1280–99. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.78.","ieee":"J. Augustine, K. Hinnenthal, F. Kuhn, C. Scheideler, and P. Schneider, “Shortest Paths in a Hybrid Network Model,” in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, 2020, pp. 1280–1299, doi: 10.1137/1.9781611975994.78.","short":"J. Augustine, K. Hinnenthal, F. Kuhn, C. Scheideler, P. Schneider, in: S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, SIAM, 2020, pp. 1280–1299."},"type":"conference","page":"1280-1299"},{"title":"Forming tile shapes with simple robots","user_id":"15504","volume":19,"date_created":"2020-08-11T10:57:26Z","status":"public","publication":"Nat. Comput.","author":[{"last_name":"Gmyr","full_name":"Gmyr, Robert","first_name":"Robert"},{"last_name":"Hinnenthal","id":"32229","first_name":"Kristian","full_name":"Hinnenthal, Kristian"},{"full_name":"Kostitsyna, Irina","first_name":"Irina","last_name":"Kostitsyna"},{"full_name":"Kuhn, Fabian","first_name":"Fabian","last_name":"Kuhn"},{"first_name":"Dorian","full_name":"Rudolph, Dorian","last_name":"Rudolph"},{"last_name":"Scheideler","id":"20792","first_name":"Christian","full_name":"Scheideler, Christian"},{"last_name":"Strothmann","full_name":"Strothmann, Thim","first_name":"Thim"}],"doi":"10.1007/s11047-019-09774-2","issue":"2","_id":"17808","date_updated":"2022-01-06T06:53:20Z","intvolume":" 19","page":"375-390","year":"2020","citation":{"chicago":"Gmyr, Robert, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, and Thim Strothmann. “Forming Tile Shapes with Simple Robots.” Nat. Comput. 19, no. 2 (2020): 375–90. https://doi.org/10.1007/s11047-019-09774-2.","apa":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., & Strothmann, T. (2020). Forming tile shapes with simple robots. Nat. Comput., 19(2), 375–390. https://doi.org/10.1007/s11047-019-09774-2","ama":"Gmyr R, Hinnenthal K, Kostitsyna I, et al. Forming tile shapes with simple robots. Nat Comput. 2020;19(2):375-390. doi:10.1007/s11047-019-09774-2","bibtex":"@article{Gmyr_Hinnenthal_Kostitsyna_Kuhn_Rudolph_Scheideler_Strothmann_2020, title={Forming tile shapes with simple robots}, volume={19}, DOI={10.1007/s11047-019-09774-2}, number={2}, journal={Nat. Comput.}, author={Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim}, year={2020}, pages={375–390} }","mla":"Gmyr, Robert, et al. “Forming Tile Shapes with Simple Robots.” Nat. Comput., vol. 19, no. 2, 2020, pp. 375–90, doi:10.1007/s11047-019-09774-2.","short":"R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, T. Strothmann, Nat. Comput. 19 (2020) 375–390.","ieee":"R. Gmyr et al., “Forming tile shapes with simple robots,” Nat. Comput., vol. 19, no. 2, pp. 375–390, 2020."},"type":"journal_article","language":[{"iso":"eng"}]},{"title":"Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs","external_id":{"arxiv":["2007.01191"]},"project":[{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"name":"SFB 901","_id":"1"}],"department":[{"_id":"79"}],"doi":"10.4230/LIPIcs.OPODIS.2020.31","date_updated":"2022-01-06T06:54:36Z","language":[{"iso":"eng"}],"ddc":["000"],"user_id":"23538","abstract":[{"lang":"eng","text":"We consider the problem of computing shortest paths in \\emph{hybrid networks}, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a \\emph{local} and a \\emph{global} mode. Specifically, the local edges model a fixed communication network in which $O(1)$ messages of size $O(\\log n)$ can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most $O(\\log n)$ messages over global edges, which restricts the nodes to use these edges only very sparsely.\r\n\r\nWe demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in \\emph{sparse graphs}. Specifically, we present exact $O(\\log n)$ time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges and arboricity $O(\\log n)$. For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model.\r\nBeyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.\r\n"}],"date_created":"2020-12-16T10:20:18Z","has_accepted_license":"1","status":"public","publication":"Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)","file_date_updated":"2020-12-16T10:18:50Z","author":[{"id":"23538","last_name":"Feldmann","full_name":"Feldmann, Michael","first_name":"Michael"},{"id":"32229","last_name":"Hinnenthal","full_name":"Hinnenthal, Kristian","first_name":"Kristian"},{"full_name":"Scheideler, Christian","first_name":"Christian","id":"20792","last_name":"Scheideler"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"date_updated":"2020-12-16T10:18:50Z","content_type":"application/pdf","success":1,"relation":"main_file","file_size":867373,"creator":"mfeldma2","file_id":"20756","access_level":"closed","date_created":"2020-12-16T10:18:50Z","file_name":"Fast_Hybrid_Network_Algorithms_for_Shortest_Paths_in_Sparse_Graphs.pdf"}],"_id":"20755","citation":{"ieee":"M. Feldmann, K. Hinnenthal, and C. Scheideler, “Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs,” in Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), 2020.","short":"M. Feldmann, K. Hinnenthal, C. Scheideler, in: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","bibtex":"@inproceedings{Feldmann_Hinnenthal_Scheideler_2020, title={Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs}, DOI={10.4230/LIPIcs.OPODIS.2020.31}, booktitle={Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={Feldmann, Michael and Hinnenthal, Kristian and Scheideler, Christian}, year={2020} }","mla":"Feldmann, Michael, et al. “Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs.” Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.OPODIS.2020.31.","apa":"Feldmann, M., Hinnenthal, K., & Scheideler, C. (2020). Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2020.31","ama":"Feldmann M, Hinnenthal K, Scheideler C. Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS). Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.OPODIS.2020.31","chicago":"Feldmann, Michael, Kristian Hinnenthal, and Christian Scheideler. “Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs.” In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2020.31."},"year":"2020","type":"conference"},{"type":"conference","year":"2020","citation":{"ama":"Daymude JJ, Gmyr R, Hinnenthal K, Kostitsyna I, Scheideler C, Richa AW. Convex Hull Formation for Programmable Matter. In: Proceedings of the 21st International Conference on Distributed Computing and Networking. ; 2020. doi:10.1145/3369740.3372916","apa":"Daymude, J. J., Gmyr, R., Hinnenthal, K., Kostitsyna, I., Scheideler, C., & Richa, A. W. (2020). Convex Hull Formation for Programmable Matter. In Proceedings of the 21st International Conference on Distributed Computing and Networking. https://doi.org/10.1145/3369740.3372916","chicago":"Daymude, Joshua J., Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, and Andréa W. Richa. “Convex Hull Formation for Programmable Matter.” In Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020. https://doi.org/10.1145/3369740.3372916.","mla":"Daymude, Joshua J., et al. “Convex Hull Formation for Programmable Matter.” Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020, doi:10.1145/3369740.3372916.","bibtex":"@inproceedings{Daymude_Gmyr_Hinnenthal_Kostitsyna_Scheideler_Richa_2020, title={Convex Hull Formation for Programmable Matter}, DOI={10.1145/3369740.3372916}, booktitle={Proceedings of the 21st International Conference on Distributed Computing and Networking}, author={Daymude, Joshua J. and Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Scheideler, Christian and Richa, Andréa W.}, year={2020} }","short":"J.J. Daymude, R. Gmyr, K. Hinnenthal, I. Kostitsyna, C. Scheideler, A.W. Richa, in: Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020.","ieee":"J. J. Daymude, R. Gmyr, K. Hinnenthal, I. Kostitsyna, C. Scheideler, and A. W. Richa, “Convex Hull Formation for Programmable Matter,” in Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020."},"language":[{"iso":"eng"}],"_id":"16346","date_updated":"2022-01-06T06:52:49Z","doi":"10.1145/3369740.3372916","publication":"Proceedings of the 21st International Conference on Distributed Computing and Networking","author":[{"full_name":"Daymude, Joshua J.","first_name":"Joshua J.","last_name":"Daymude"},{"last_name":"Gmyr","first_name":"Robert","full_name":"Gmyr, Robert"},{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"},{"full_name":"Kostitsyna, Irina","first_name":"Irina","last_name":"Kostitsyna"},{"first_name":"Christian","full_name":"Scheideler, Christian","last_name":"Scheideler","id":"20792"},{"last_name":"Richa","full_name":"Richa, Andréa W.","first_name":"Andréa W."}],"publication_status":"published","publication_identifier":{"isbn":["9781450377515"]},"date_created":"2020-03-26T07:33:41Z","status":"public","title":"Convex Hull Formation for Programmable Matter","user_id":"32229"},{"doi":"10.1145/3323165.3323195","date_updated":"2022-01-06T07:04:04Z","language":[{"iso":"eng"}],"title":"Distributed Computation in Node-Capacitated Networks","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"department":[{"_id":"79"}],"_id":"8871","year":"2019","citation":{"short":"J. Augustine, M. Ghaffari, R. Gmyr, K. Hinnenthal, F. Kuhn, J. Li, C. Scheideler, in: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2019, pp. 69--79.","ieee":"J. Augustine et al., “Distributed Computation in Node-Capacitated Networks,” in Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019, pp. 69--79.","chicago":"Augustine, John, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, and Christian Scheideler. “Distributed Computation in Node-Capacitated Networks.” In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, 69--79. ACM, 2019. https://doi.org/10.1145/3323165.3323195.","ama":"Augustine J, Ghaffari M, Gmyr R, et al. Distributed Computation in Node-Capacitated Networks. In: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. ACM; 2019:69--79. doi:10.1145/3323165.3323195","apa":"Augustine, J., Ghaffari, M., Gmyr, R., Hinnenthal, K., Kuhn, F., Li, J., & Scheideler, C. (2019). Distributed Computation in Node-Capacitated Networks. In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (pp. 69--79). ACM. https://doi.org/10.1145/3323165.3323195","bibtex":"@inproceedings{Augustine_Ghaffari_Gmyr_Hinnenthal_Kuhn_Li_Scheideler_2019, title={Distributed Computation in Node-Capacitated Networks}, DOI={10.1145/3323165.3323195}, booktitle={Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures}, publisher={ACM}, author={Augustine, John and Ghaffari, Mohsen and Gmyr, Robert and Hinnenthal, Kristian and Kuhn, Fabian and Li, Jason and Scheideler, Christian}, year={2019}, pages={69--79} }","mla":"Augustine, John, et al. “Distributed Computation in Node-Capacitated Networks.” Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2019, pp. 69--79, doi:10.1145/3323165.3323195."},"type":"conference","page":"69--79","ddc":["004"],"user_id":"477","status":"public","has_accepted_license":"1","date_created":"2019-04-10T08:20:34Z","author":[{"first_name":"John","full_name":"Augustine, John","last_name":"Augustine"},{"last_name":"Ghaffari","first_name":"Mohsen","full_name":"Ghaffari, Mohsen"},{"last_name":"Gmyr","full_name":"Gmyr, Robert","first_name":"Robert"},{"first_name":"Kristian","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal","id":"32229"},{"full_name":"Kuhn, Fabian","first_name":"Fabian","last_name":"Kuhn"},{"first_name":"Jason","full_name":"Li, Jason","last_name":"Li"},{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"}],"publisher":"ACM","publication":"Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures","file_date_updated":"2019-08-26T11:17:58Z","file":[{"file_id":"12964","creator":"ups","file_size":1275192,"relation":"main_file","success":1,"date_updated":"2019-08-26T11:17:58Z","content_type":"application/pdf","file_name":"p69-augustine.pdf","date_created":"2019-08-26T11:17:58Z","access_level":"closed"}]},{"date_created":"2019-05-02T09:38:58Z","status":"public","publication":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing.","author":[{"last_name":"Daymude","first_name":"Joshua J.","full_name":"Daymude, Joshua J."},{"last_name":"Hinnenthal","id":"32229","first_name":"Kristian","full_name":"Hinnenthal, Kristian"},{"full_name":"Richa, Andréa W.","first_name":"Andréa W.","last_name":"Richa"},{"last_name":"Scheideler","id":"20792","first_name":"Christian","full_name":"Scheideler, Christian"}],"publisher":"Springer, Cham","user_id":"32229","title":"Computing by Programmable Particles","language":[{"iso":"eng"}],"page":"615-681","year":"2019","type":"book_chapter","citation":{"ieee":"J. J. Daymude, K. Hinnenthal, A. W. Richa, and C. Scheideler, “Computing by Programmable Particles,” in Distributed Computing by Mobile Entities, Current Research in Moving and Computing., Springer, Cham, 2019, pp. 615–681.","short":"J.J. Daymude, K. Hinnenthal, A.W. Richa, C. Scheideler, in: Distributed Computing by Mobile Entities, Current Research in Moving and Computing., Springer, Cham, 2019, pp. 615–681.","mla":"Daymude, Joshua J., et al. “Computing by Programmable Particles.” Distributed Computing by Mobile Entities, Current Research in Moving and Computing., Springer, Cham, 2019, pp. 615–81, doi:https://doi.org/10.1007/978-3-030-11072-7_22.","bibtex":"@inbook{Daymude_Hinnenthal_Richa_Scheideler_2019, title={Computing by Programmable Particles}, DOI={https://doi.org/10.1007/978-3-030-11072-7_22}, booktitle={Distributed Computing by Mobile Entities, Current Research in Moving and Computing.}, publisher={Springer, Cham}, author={Daymude, Joshua J. and Hinnenthal, Kristian and Richa, Andréa W. and Scheideler, Christian}, year={2019}, pages={615–681} }","chicago":"Daymude, Joshua J., Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. “Computing by Programmable Particles.” In Distributed Computing by Mobile Entities, Current Research in Moving and Computing., 615–81. Springer, Cham, 2019. https://doi.org/10.1007/978-3-030-11072-7_22.","apa":"Daymude, J. J., Hinnenthal, K., Richa, A. W., & Scheideler, C. (2019). Computing by Programmable Particles. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing. (pp. 615–681). Springer, Cham. https://doi.org/10.1007/978-3-030-11072-7_22","ama":"Daymude JJ, Hinnenthal K, Richa AW, Scheideler C. Computing by Programmable Particles. In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Springer, Cham; 2019:615-681. doi:https://doi.org/10.1007/978-3-030-11072-7_22"},"doi":"https://doi.org/10.1007/978-3-030-11072-7_22","_id":"9599","date_updated":"2022-01-06T07:04:16Z"},{"title":"Faster Construction of Overlay Networks","user_id":"32229","place":"Cham","publication_status":"published","date_created":"2019-08-19T07:18:57Z","status":"public","publication":"Structural Information and Communication Complexity","author":[{"id":"34727","last_name":"Götte","full_name":"Götte, Thorsten","first_name":"Thorsten"},{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"},{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"}],"doi":"10.1007/978-3-030-24922-9_18","date_updated":"2022-01-06T06:51:27Z","_id":"12944","type":"conference","year":"2019","citation":{"short":"T. Götte, K. Hinnenthal, C. Scheideler, in: Structural Information and Communication Complexity, Cham, 2019.","ieee":"T. Götte, K. Hinnenthal, and C. Scheideler, “Faster Construction of Overlay Networks,” in Structural Information and Communication Complexity, 2019.","apa":"Götte, T., Hinnenthal, K., & Scheideler, C. (2019). Faster Construction of Overlay Networks. In Structural Information and Communication Complexity. Cham. https://doi.org/10.1007/978-3-030-24922-9_18","ama":"Götte T, Hinnenthal K, Scheideler C. Faster Construction of Overlay Networks. In: Structural Information and Communication Complexity. Cham; 2019. doi:10.1007/978-3-030-24922-9_18","chicago":"Götte, Thorsten, Kristian Hinnenthal, and Christian Scheideler. “Faster Construction of Overlay Networks.” In Structural Information and Communication Complexity. Cham, 2019. https://doi.org/10.1007/978-3-030-24922-9_18.","mla":"Götte, Thorsten, et al. “Faster Construction of Overlay Networks.” Structural Information and Communication Complexity, 2019, doi:10.1007/978-3-030-24922-9_18.","bibtex":"@inproceedings{Götte_Hinnenthal_Scheideler_2019, place={Cham}, title={Faster Construction of Overlay Networks}, DOI={10.1007/978-3-030-24922-9_18}, booktitle={Structural Information and Communication Complexity}, author={Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian}, year={2019} }"},"language":[{"iso":"eng"}]},{"place":"Philadelphia, PA","user_id":"32229","title":"Shortest Paths in a Hybrid Network Model","author":[{"last_name":"Augustine","first_name":"John","full_name":"Augustine, John"},{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"},{"first_name":"Fabian","full_name":"Kuhn, Fabian","last_name":"Kuhn"},{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"},{"full_name":"Schneider, Philipp","first_name":"Philipp","last_name":"Schneider"}],"publication":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","status":"public","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"date_created":"2020-01-22T09:07:36Z","publication_status":"published","publication_identifier":{"isbn":["9781611975994"]},"date_updated":"2022-01-06T06:52:30Z","_id":"15627","doi":"10.1137/1.9781611975994.78","language":[{"iso":"eng"}],"type":"conference","citation":{"ieee":"J. Augustine, K. Hinnenthal, F. Kuhn, C. Scheideler, and P. Schneider, “Shortest Paths in a Hybrid Network Model,” in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 1280–1299.","short":"J. Augustine, K. Hinnenthal, F. Kuhn, C. Scheideler, P. Schneider, in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, 2019, pp. 1280–1299.","mla":"Augustine, John, et al. “Shortest Paths in a Hybrid Network Model.” Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 1280–99, doi:10.1137/1.9781611975994.78.","bibtex":"@inproceedings{Augustine_Hinnenthal_Kuhn_Scheideler_Schneider_2019, place={Philadelphia, PA}, title={Shortest Paths in a Hybrid Network Model}, DOI={10.1137/1.9781611975994.78}, booktitle={Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms}, author={Augustine, John and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp}, year={2019}, pages={1280–1299} }","chicago":"Augustine, John, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. “Shortest Paths in a Hybrid Network Model.” In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1280–99. Philadelphia, PA, 2019. https://doi.org/10.1137/1.9781611975994.78.","ama":"Augustine J, Hinnenthal K, Kuhn F, Scheideler C, Schneider P. Shortest Paths in a Hybrid Network Model. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA; 2019:1280-1299. doi:10.1137/1.9781611975994.78","apa":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., & Schneider, P. (2019). Shortest Paths in a Hybrid Network Model. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1280–1299). Philadelphia, PA. https://doi.org/10.1137/1.9781611975994.78"},"year":"2019","page":"1280-1299"},{"user_id":"32229","title":"Fast Distributed Algorithms for LP-Type Problems of Low Dimension","status":"public","date_created":"2019-10-08T11:53:38Z","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"author":[{"id":"32229","last_name":"Hinnenthal","full_name":"Hinnenthal, Kristian","first_name":"Kristian"},{"full_name":"Scheideler, Christian","first_name":"Christian","id":"20792","last_name":"Scheideler"},{"last_name":"Struijs","first_name":"Martijn","full_name":"Struijs, Martijn"}],"department":[{"_id":"79"}],"publication":"33rd International Symposium on Distributed Computing (DISC 2019)","doi":"10.4230/LIPICS.DISC.2019.23","_id":"13652","date_updated":"2022-01-06T06:51:41Z","language":[{"iso":"eng"}],"year":"2019","citation":{"mla":"Hinnenthal, Kristian, et al. “Fast Distributed Algorithms for LP-Type Problems of Low Dimension.” 33rd International Symposium on Distributed Computing (DISC 2019), 2019, doi:10.4230/LIPICS.DISC.2019.23.","bibtex":"@inproceedings{Hinnenthal_Scheideler_Struijs_2019, title={Fast Distributed Algorithms for LP-Type Problems of Low Dimension}, DOI={10.4230/LIPICS.DISC.2019.23}, booktitle={33rd International Symposium on Distributed Computing (DISC 2019)}, author={Hinnenthal, Kristian and Scheideler, Christian and Struijs, Martijn}, year={2019} }","chicago":"Hinnenthal, Kristian, Christian Scheideler, and Martijn Struijs. “Fast Distributed Algorithms for LP-Type Problems of Low Dimension.” In 33rd International Symposium on Distributed Computing (DISC 2019), 2019. https://doi.org/10.4230/LIPICS.DISC.2019.23.","ama":"Hinnenthal K, Scheideler C, Struijs M. Fast Distributed Algorithms for LP-Type Problems of Low Dimension. In: 33rd International Symposium on Distributed Computing (DISC 2019). ; 2019. doi:10.4230/LIPICS.DISC.2019.23","apa":"Hinnenthal, K., Scheideler, C., & Struijs, M. (2019). Fast Distributed Algorithms for LP-Type Problems of Low Dimension. In 33rd International Symposium on Distributed Computing (DISC 2019). https://doi.org/10.4230/LIPICS.DISC.2019.23","ieee":"K. Hinnenthal, C. Scheideler, and M. Struijs, “Fast Distributed Algorithms for LP-Type Problems of Low Dimension,” in 33rd International Symposium on Distributed Computing (DISC 2019), 2019.","short":"K. Hinnenthal, C. Scheideler, M. Struijs, in: 33rd International Symposium on Distributed Computing (DISC 2019), 2019."},"type":"conference"},{"title":"Forming Tile Shapes with Simple Robots","user_id":"11319","publication":"Proceedings of the 24th International Conference on DNA Computing and Molecular Programming","department":[{"_id":"79"},{"_id":"66"}],"author":[{"full_name":"Gmyr, Robert","first_name":"Robert","last_name":"Gmyr"},{"last_name":"Hinnenthal","id":"32229","first_name":"Kristian","full_name":"Hinnenthal, Kristian"},{"last_name":"Kostitsyna","first_name":"Irina","full_name":"Kostitsyna, Irina"},{"first_name":"Fabian","full_name":"Kuhn, Fabian","last_name":"Kuhn"},{"last_name":"Rudolph","first_name":"Dorian","full_name":"Rudolph, Dorian"},{"full_name":"Scheideler, Christian","first_name":"Christian","id":"20792","last_name":"Scheideler"},{"full_name":"Strothmann, Thim Frederik","first_name":"Thim Frederik","id":"11319","last_name":"Strothmann"}],"publisher":"Springer International Publishing","publication_status":"published","date_created":"2018-11-19T15:35:45Z","status":"public","date_updated":"2022-01-06T07:02:38Z","_id":"5764","doi":"10.1007/978-3-030-00030-1_8","page":"122-138","citation":{"chicago":"Gmyr, Robert, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, and Thim Frederik Strothmann. “Forming Tile Shapes with Simple Robots.” In Proceedings of the 24th International Conference on DNA Computing and Molecular Programming, 122–38. Springer International Publishing, 2018. https://doi.org/10.1007/978-3-030-00030-1_8.","ama":"Gmyr R, Hinnenthal K, Kostitsyna I, et al. Forming Tile Shapes with Simple Robots. In: Proceedings of the 24th International Conference on DNA Computing and Molecular Programming. Springer International Publishing; 2018:122-138. doi:10.1007/978-3-030-00030-1_8","apa":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., & Strothmann, T. F. (2018). Forming Tile Shapes with Simple Robots. In Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (pp. 122–138). Springer International Publishing. https://doi.org/10.1007/978-3-030-00030-1_8","mla":"Gmyr, Robert, et al. “Forming Tile Shapes with Simple Robots.” Proceedings of the 24th International Conference on DNA Computing and Molecular Programming, Springer International Publishing, 2018, pp. 122–38, doi:10.1007/978-3-030-00030-1_8.","bibtex":"@inproceedings{Gmyr_Hinnenthal_Kostitsyna_Kuhn_Rudolph_Scheideler_Strothmann_2018, title={Forming Tile Shapes with Simple Robots}, DOI={10.1007/978-3-030-00030-1_8}, booktitle={Proceedings of the 24th International Conference on DNA Computing and Molecular Programming}, publisher={Springer International Publishing}, author={Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim Frederik}, year={2018}, pages={122–138} }","short":"R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, T.F. Strothmann, in: Proceedings of the 24th International Conference on DNA Computing and Molecular Programming, Springer International Publishing, 2018, pp. 122–138.","ieee":"R. Gmyr et al., “Forming Tile Shapes with Simple Robots,” in Proceedings of the 24th International Conference on DNA Computing and Molecular Programming, 2018, pp. 122–138."},"year":"2018","type":"conference","language":[{"iso":"eng"}]},{"title":"Shape Recognition by a Finite Automaton Robot","user_id":"15504","date_created":"2018-11-30T08:13:58Z","status":"public","department":[{"_id":"79"}],"publication":"43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK","author":[{"last_name":"Gmyr","full_name":"Gmyr, Robert","first_name":"Robert"},{"last_name":"Hinnenthal","id":"32229","first_name":"Kristian","full_name":"Hinnenthal, Kristian"},{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"first_name":"Fabian","full_name":"Kuhn, Fabian","last_name":"Kuhn"},{"last_name":"Rudolph","full_name":"Rudolph, Dorian","first_name":"Dorian"},{"full_name":"Scheideler, Christian","first_name":"Christian","id":"20792","last_name":"Scheideler"}],"doi":"10.4230/LIPIcs.MFCS.2018.52","date_updated":"2022-01-06T07:02:49Z","_id":"5986","page":"52:1-52:15","type":"conference","year":"2018","citation":{"apa":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., & Scheideler, C. (2018). Shape Recognition by a Finite Automaton Robot. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK (pp. 52:1-52:15). https://doi.org/10.4230/LIPIcs.MFCS.2018.52","ama":"Gmyr R, Hinnenthal K, Kostitsyna I, Kuhn F, Rudolph D, Scheideler C. Shape Recognition by a Finite Automaton Robot. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK. ; 2018:52:1-52:15. doi:10.4230/LIPIcs.MFCS.2018.52","chicago":"Gmyr, Robert, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler. “Shape Recognition by a Finite Automaton Robot.” In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 52:1-52:15, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.52.","mla":"Gmyr, Robert, et al. “Shape Recognition by a Finite Automaton Robot.” 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 2018, pp. 52:1-52:15, doi:10.4230/LIPIcs.MFCS.2018.52.","bibtex":"@inproceedings{Gmyr_Hinnenthal_Kostitsyna_Kuhn_Rudolph_Scheideler_2018, title={Shape Recognition by a Finite Automaton Robot}, DOI={10.4230/LIPIcs.MFCS.2018.52}, booktitle={43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK}, author={Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian}, year={2018}, pages={52:1-52:15} }","short":"R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, in: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 2018, pp. 52:1-52:15.","ieee":"R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, and C. Scheideler, “Shape Recognition by a Finite Automaton Robot,” in 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 2018, pp. 52:1-52:15."},"language":[{"iso":"eng"}]},{"ddc":["040"],"user_id":"20792","abstract":[{"text":"We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.","lang":"eng"}],"status":"public","has_accepted_license":"1","date_created":"2017-10-17T12:41:12Z","author":[{"full_name":"Gmyr, Robert","first_name":"Robert","last_name":"Gmyr"},{"id":"32229","last_name":"Hinnenthal","full_name":"Hinnenthal, Kristian","first_name":"Kristian"},{"last_name":"Scheideler","id":"20792","first_name":"Christian","full_name":"Scheideler, Christian"},{"last_name":"Sohler","first_name":"Christian","full_name":"Sohler, Christian"}],"file_date_updated":"2018-03-13T09:23:11Z","publication":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)","file":[{"creator":"florida","file_id":"1207","file_size":504161,"relation":"main_file","success":1,"content_type":"application/pdf","date_updated":"2018-03-13T09:23:11Z","date_created":"2018-03-13T09:23:11Z","file_name":"105-ICALP17-GHSS.pdf","access_level":"closed"}],"_id":"105","type":"conference","year":"2017","citation":{"chicago":"Gmyr, Robert, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. “Distributed Monitoring of Network Properties: The Power of Hybrid Networks.” In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 137:1--137:15. Leibniz International Proceedings in Informatics (LIPIcs), 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.137.","ama":"Gmyr R, Hinnenthal K, Scheideler C, Sohler C. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). Leibniz International Proceedings in Informatics (LIPIcs). ; 2017:137:1--137:15. doi:10.4230/LIPIcs.ICALP.2017.137","apa":"Gmyr, R., Hinnenthal, K., Scheideler, C., & Sohler, C. (2017). Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP) (pp. 137:1--137:15). https://doi.org/10.4230/LIPIcs.ICALP.2017.137","bibtex":"@inproceedings{Gmyr_Hinnenthal_Scheideler_Sohler_2017, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Distributed Monitoring of Network Properties: The Power of Hybrid Networks}, DOI={10.4230/LIPIcs.ICALP.2017.137}, booktitle={Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)}, author={Gmyr, Robert and Hinnenthal, Kristian and Scheideler, Christian and Sohler, Christian}, year={2017}, pages={137:1--137:15}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","mla":"Gmyr, Robert, et al. “Distributed Monitoring of Network Properties: The Power of Hybrid Networks.” Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1--137:15, doi:10.4230/LIPIcs.ICALP.2017.137.","short":"R. Gmyr, K. Hinnenthal, C. Scheideler, C. Sohler, in: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1--137:15.","ieee":"R. Gmyr, K. Hinnenthal, C. Scheideler, and C. Sohler, “Distributed Monitoring of Network Properties: The Power of Hybrid Networks,” in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1--137:15."},"page":"137:1--137:15","title":"Distributed Monitoring of Network Properties: The Power of Hybrid Networks","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"department":[{"_id":"79"}],"doi":"10.4230/LIPIcs.ICALP.2017.137","date_updated":"2022-01-06T06:50:42Z","language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)"},{"abstract":[{"text":"We consider the problem of aggregation in overlay networks. We use a synchronous time model in which each node has polylogarithmic memory and can send at most a polylogarithmic number of messages per round. We investigate how to quickly compute the result of an aggregate functionf over elements that are distributed among the nodes of the network such that the result is eventually known by a selected root node. We show how to compute distributive aggregate functions such as SUM, MAX, and OR in time $O(\\log n / \\log\\log n)$ using a tree that is created in a pre-processing phase. If only a polylogarithmic number of data items need to be aggregated, we show how to compute the result in time $O(\\sqrt{\\log n / \\log\\log n})$. Furthermore, we show how to compute holistic aggregate functions such as DISTINCT, SMALLEST(k) and MODE(k) in time $O(\\log n / \\log\\log n)$. Finally, we show a lower bound of $\\Omega(\\sqrt{\\log n / \\log\\log n})$ for deterministic algorithms that compute any of the aggregate functions in the scope of the thesis.","lang":"eng"}],"title":"Aggregation in Overlay Networks","ddc":["040"],"user_id":"15504","department":[{"_id":"79"}],"file_date_updated":"2018-03-21T10:35:39Z","publisher":"Universität Paderborn","author":[{"first_name":"Kristian","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal","id":"32229"}],"file":[{"file_size":1127144,"creator":"florida","file_id":"1510","date_updated":"2018-03-21T10:35:39Z","content_type":"application/pdf","success":1,"relation":"main_file","date_created":"2018-03-21T10:35:39Z","file_name":"223-MasterarbeitHinnenthal.pdf","access_level":"closed"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt C1","_id":"13"},{"name":"SFB 901 - Project Area C","_id":"4"}],"date_created":"2017-10-17T12:41:35Z","has_accepted_license":"1","status":"public","date_updated":"2022-01-06T06:55:30Z","_id":"223","citation":{"apa":"Hinnenthal, K. (2016). Aggregation in Overlay Networks. Universität Paderborn.","ama":"Hinnenthal K. Aggregation in Overlay Networks. Universität Paderborn; 2016.","chicago":"Hinnenthal, Kristian. Aggregation in Overlay Networks. Universität Paderborn, 2016.","bibtex":"@book{Hinnenthal_2016, title={Aggregation in Overlay Networks}, publisher={Universität Paderborn}, author={Hinnenthal, Kristian}, year={2016} }","mla":"Hinnenthal, Kristian. Aggregation in Overlay Networks. Universität Paderborn, 2016.","short":"K. Hinnenthal, Aggregation in Overlay Networks, Universität Paderborn, 2016.","ieee":"K. Hinnenthal, Aggregation in Overlay Networks. Universität Paderborn, 2016."},"type":"mastersthesis","year":"2016","language":[{"iso":"eng"}],"supervisor":[{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"}]},{"title":"Formbildung selbstorganisierender Partikelsysteme","user_id":"15504","status":"public","date_created":"2020-08-17T08:17:00Z","author":[{"full_name":"Hinnenthal, Kristian","first_name":"Kristian","id":"32229","last_name":"Hinnenthal"}],"department":[{"_id":"79"}],"_id":"18002","date_updated":"2022-01-06T06:53:25Z","type":"bachelorsthesis","citation":{"ieee":"K. Hinnenthal, Formbildung selbstorganisierender Partikelsysteme. 2014.","short":"K. Hinnenthal, Formbildung Selbstorganisierender Partikelsysteme, 2014.","bibtex":"@book{Hinnenthal_2014, title={Formbildung selbstorganisierender Partikelsysteme}, author={Hinnenthal, Kristian}, year={2014} }","mla":"Hinnenthal, Kristian. Formbildung Selbstorganisierender Partikelsysteme. 2014.","ama":"Hinnenthal K. Formbildung Selbstorganisierender Partikelsysteme.; 2014.","apa":"Hinnenthal, K. (2014). Formbildung selbstorganisierender Partikelsysteme.","chicago":"Hinnenthal, Kristian. Formbildung Selbstorganisierender Partikelsysteme, 2014."},"year":"2014","language":[{"iso":"eng"}],"supervisor":[{"last_name":"Scheideler","id":"20792","first_name":"Christian","full_name":"Scheideler, Christian"}]}]