[{"_id":"62285","user_id":"15578","department":[{"_id":"79"}],"type":"conference","editor":[{"first_name":"Silvia","last_name":"Bonomi","full_name":"Bonomi, Silvia"},{"full_name":"Mandal, Partha Sarathi","last_name":"Mandal","first_name":"Partha Sarathi"},{"last_name":"Robinson","full_name":"Robinson, Peter","first_name":"Peter"},{"last_name":"Sharma","full_name":"Sharma, Gokarna","first_name":"Gokarna"},{"first_name":"Sebastien","last_name":"Tixeuil","full_name":"Tixeuil, Sebastien"}],"status":"public","date_updated":"2026-02-11T08:31:14Z","author":[{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"first_name":"David Jan","last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557"},{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"}],"doi":"10.1007/978-3-032-11127-2_26","conference":{"name":"27th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","start_date":"2025-10-09","end_date":"2025-10-11","location":"Kathmandu"},"publication_status":"published","publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783032111265","9783032111272"]},"place":"Cham","citation":{"bibtex":"@inproceedings{Kostitsyna_Liedtke_Scheideler_2025, place={Cham}, title={Invited Paper: Distributed Rhombus Formation of Sliding Squares}, DOI={<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>}, booktitle={Stabilization, Safety, and Security of Distributed Systems}, publisher={Springer Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}, editor={Bonomi, Silvia and Mandal, Partha Sarathi and Robinson, Peter and Sharma, Gokarna and Tixeuil, Sebastien}, year={2025}, pages={325–342} }","short":"I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: S. Bonomi, P.S. Mandal, P. Robinson, G. Sharma, S. Tixeuil (Eds.), Stabilization, Safety, and Security of Distributed Systems, Springer Nature Switzerland, Cham, 2025, pp. 325–342.","mla":"Kostitsyna, Irina, et al. “Invited Paper: Distributed Rhombus Formation of Sliding Squares.” <i>Stabilization, Safety, and Security of Distributed Systems</i>, edited by Silvia Bonomi et al., Springer Nature Switzerland, 2025, pp. 325–42, doi:<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>.","apa":"Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2025). Invited Paper: Distributed Rhombus Formation of Sliding Squares. In S. Bonomi, P. S. Mandal, P. Robinson, G. Sharma, &#38; S. Tixeuil (Eds.), <i>Stabilization, Safety, and Security of Distributed Systems</i> (pp. 325–342). Springer Nature Switzerland. <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">https://doi.org/10.1007/978-3-032-11127-2_26</a>","ama":"Kostitsyna I, Liedtke DJ, Scheideler C. Invited Paper: Distributed Rhombus Formation of Sliding Squares. In: Bonomi S, Mandal PS, Robinson P, Sharma G, Tixeuil S, eds. <i>Stabilization, Safety, and Security of Distributed Systems</i>. Springer Nature Switzerland; 2025:325-342. doi:<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>","chicago":"Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Invited Paper: Distributed Rhombus Formation of Sliding Squares.” In <i>Stabilization, Safety, and Security of Distributed Systems</i>, edited by Silvia Bonomi, Partha Sarathi Mandal, Peter Robinson, Gokarna Sharma, and Sebastien Tixeuil, 325–42. Cham: Springer Nature Switzerland, 2025. <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">https://doi.org/10.1007/978-3-032-11127-2_26</a>.","ieee":"I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Invited Paper: Distributed Rhombus Formation of Sliding Squares,” in <i>Stabilization, Safety, and Security of Distributed Systems</i>, Kathmandu, 2025, pp. 325–342, doi: <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>."},"page":"325-342","language":[{"iso":"eng"}],"publication":"Stabilization, Safety, and Security of Distributed Systems","abstract":[{"lang":"eng","text":"The sliding square model is a widely used abstraction for studying self-reconfigurable robotic systems, where modules are square-shaped robots that move by sliding or rotating over one another. In this paper, we propose a novel distributed algorithm that enables a group of modules to reconfigure into a rhombus shape, starting from an arbitrary side-connected configuration. It is connectivity-preserving and operates under minimal assumptions: one leader module, common chirality, constant memory per module, and visibility and communication restricted to immediate neighbors. Unlike prior work, which relaxes the original sliding square move-set, our approach uses the unmodified move-set, addressing the additional challenge of handling locked configurations. Our algorithm is sequential in nature and operates with a worst-case time complexity of O(n^2) rounds, which is optimal for sequential algorithms. To improve runtime, we introduce two parallel variants of the algorithm. Both rely on a spanning tree data structure, allowing modules to make decisions based on local connectivity. Our experimental results show a significant speedup for the first variant, and a linear average runtime for the second variant, which is worst-case optimal for parallel algorithms."}],"publisher":"Springer Nature Switzerland","date_created":"2025-11-23T21:07:12Z","title":"Invited Paper: Distributed Rhombus Formation of Sliding Squares","year":"2025"},{"type":"journal_article","publication":"Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)","status":"public","_id":"64098","user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"language":[{"iso":"eng"}],"year":"2025","citation":{"mla":"Scheideler, Christian, et al. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025).” <i>Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025)</i>, 2025.","bibtex":"@article{Scheideler_Padalkin_Kumar_2025, title={Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)}, journal={Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)}, author={Scheideler, Christian and Padalkin, Andreas and Kumar, Manish}, year={2025} }","short":"C. Scheideler, A. Padalkin, M. Kumar, Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025) (2025).","apa":"Scheideler, C., Padalkin, A., &#38; Kumar, M. (2025). Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025). <i>Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025)</i>.","ieee":"C. Scheideler, A. Padalkin, and M. Kumar, “Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025),” <i>Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)</i>, 2025.","chicago":"Scheideler, Christian, Andreas Padalkin, and Manish Kumar. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025).” <i>Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. Auton. Robots 49(3): 22 (2025)</i>, 2025.","ama":"Scheideler C, Padalkin A, Kumar M. Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025). <i>Reconfiguration and locomotion with joint movements in the amoebot model Auton Robots 49(3): 22 (2025)</i>. Published online 2025."},"date_updated":"2026-02-11T09:11:49Z","author":[{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"},{"last_name":"Padalkin","id":"88238","full_name":"Padalkin, Andreas","first_name":"Andreas"},{"last_name":"Kumar","full_name":"Kumar, Manish","first_name":"Manish"}],"date_created":"2026-02-10T09:41:12Z","title":"Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)"},{"year":"2025","place":"SoCG 2025: 81:1-81:5","citation":{"apa":"Scheideler, C., Artmann, M., Maurer, T., Padalkin, A., &#38; Warner, D. (2025). <i>AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). </i>.","short":"C. Scheideler, M. Artmann, T. Maurer, A. Padalkin, D. Warner, in: SoCG 2025: 81:1-81:5, 2025.","mla":"Scheideler, Christian, et al. <i>AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). </i>. 2025.","bibtex":"@inproceedings{Scheideler_Artmann_Maurer_Padalkin_Warner_2025, place={SoCG 2025: 81:1-81:5}, title={AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). }, author={Scheideler, Christian and Artmann, Matthias and Maurer, Tobias  and Padalkin, Andreas and Warner, Daniel}, year={2025} }","ama":"Scheideler C, Artmann M, Maurer T, Padalkin A, Warner D. AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). . In: ; 2025.","chicago":"Scheideler, Christian, Matthias Artmann, Tobias  Maurer, Andreas Padalkin, and Daniel Warner. “AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). .” SoCG 2025: 81:1-81:5, 2025.","ieee":"C. Scheideler, M. Artmann, T. Maurer, A. Padalkin, and D. Warner, “AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). ,” 2025."},"date_updated":"2026-02-11T09:11:42Z","author":[{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"last_name":"Artmann","full_name":"Artmann, Matthias","id":"63743","first_name":"Matthias"},{"first_name":"Tobias ","full_name":"Maurer, Tobias ","last_name":"Maurer"},{"id":"88238","full_name":"Padalkin, Andreas","last_name":"Padalkin","first_name":"Andreas"},{"first_name":"Daniel","last_name":"Warner","full_name":"Warner, Daniel","id":"3902"}],"date_created":"2026-02-10T09:01:15Z","title":"AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). ","type":"conference","status":"public","_id":"64094","user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"language":[{"iso":"eng"}]},{"status":"public","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","_id":"64096","citation":{"apa":"Scheideler, C., Dou, J., Götte, T., Hillebrandt, H., &#38; Werthmann, J. (2025). <i>Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. </i>.","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} }","short":"C. Scheideler, J. Dou, T. Götte, H. Hillebrandt, J. Werthmann, in: ITCS 2025: 45:1-45:26, 2025.","mla":"Scheideler, Christian, et al. <i>Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. </i>. 2025.","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.","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.","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."},"place":"ITCS 2025: 45:1-45:26","year":"2025","title":"Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. ","author":[{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"id":"92888","full_name":"Dou, Jinfeng","last_name":"Dou","first_name":"Jinfeng"},{"last_name":"Götte","full_name":"Götte, Thorsten ","first_name":"Thorsten "},{"first_name":"Henning","full_name":"Hillebrandt, Henning","id":"74425","last_name":"Hillebrandt"},{"last_name":"Werthmann","id":"50024","full_name":"Werthmann, Julian","first_name":"Julian"}],"date_created":"2026-02-10T09:10:14Z","date_updated":"2026-02-11T09:11:29Z"},{"publication_identifier":{"unknown":["ISBN 978-3-95977-368-3"]},"citation":{"apa":"Scheideler, C., &#38; Meeks, K. (Eds.). (2025). <i>4th Symposium on Algorithmic Foundations of Dynamic Networks.</i>","short":"C. Scheideler, K. Meeks, eds., 4th Symposium on Algorithmic Foundations of Dynamic Networks., SAND 2025, Liverpool, UK, June 9-11, 2025. LIPIcs 330, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","bibtex":"@book{Scheideler_Meeks_2025, place={SAND 2025, Liverpool, UK, June 9-11, 2025. LIPIcs 330, Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title={4th Symposium on Algorithmic Foundations of Dynamic Networks.}, year={2025} }","mla":"Scheideler, Christian, and Kitty Meeks, editors. <i>4th Symposium on Algorithmic Foundations of Dynamic Networks.</i> 2025.","chicago":"Scheideler, Christian, and Kitty Meeks, eds. <i>4th Symposium on Algorithmic Foundations of Dynamic Networks.</i> SAND 2025, Liverpool, UK, June 9-11, 2025. LIPIcs 330, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ieee":"C. Scheideler and K. Meeks, Eds., <i>4th Symposium on Algorithmic Foundations of Dynamic Networks.</i> SAND 2025, Liverpool, UK, June 9-11, 2025. LIPIcs 330, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"Scheideler C, Meeks K, eds. <i>4th Symposium on Algorithmic Foundations of Dynamic Networks.</i>; 2025."},"place":"SAND 2025, Liverpool, UK, June 9-11, 2025. LIPIcs 330, Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","date_created":"2026-02-10T09:49:03Z","date_updated":"2026-02-11T09:11:09Z","title":"4th Symposium on Algorithmic Foundations of Dynamic Networks.","type":"book_editor","status":"public","editor":[{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"},{"last_name":"Meeks","full_name":"Meeks, Kitty","first_name":"Kitty"}],"user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"_id":"64099","language":[{"iso":"eng"}]},{"citation":{"mla":"Scheideler, Christian, et al. <i>On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. </i>. 2025.","short":"C. Scheideler, M. Artmann, A. Padalkin, in: DISC 2025: 7:1-7:22, 2025.","bibtex":"@inproceedings{Scheideler_Artmann_Padalkin_2025, place={DISC 2025: 7:1-7:22}, title={On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. }, author={Scheideler, Christian and Artmann, Matthias and Padalkin, Andreas}, year={2025} }","apa":"Scheideler, C., Artmann, M., &#38; Padalkin, A. (2025). <i>On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. </i>.","chicago":"Scheideler, Christian, Matthias Artmann, and Andreas Padalkin. “On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. .” DISC 2025: 7:1-7:22, 2025.","ieee":"C. Scheideler, M. Artmann, and A. Padalkin, “On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. ,” 2025.","ama":"Scheideler C, Artmann M, Padalkin A. On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. . In: ; 2025."},"year":"2025","place":"DISC 2025: 7:1-7:22","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"first_name":"Matthias","id":"63743","full_name":"Artmann, Matthias","last_name":"Artmann"},{"first_name":"Andreas","last_name":"Padalkin","full_name":"Padalkin, Andreas","id":"88238"}],"date_created":"2026-02-10T09:17:54Z","date_updated":"2026-02-11T09:11:19Z","title":"On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. ","type":"conference","status":"public","user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"_id":"64097","language":[{"iso":"eng"}]},{"status":"public","type":"conference","language":[{"iso":"eng"}],"user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"_id":"64095","citation":{"ama":"Scheideler C, Augustine  J, Werthmann J. Supervised Distributed Computing. . In: ; 2025.","ieee":"C. Scheideler, J. Augustine , and J. Werthmann, “Supervised Distributed Computing. ,” 2025.","chicago":"Scheideler, Christian, John  Augustine , and Julian Werthmann. “Supervised Distributed Computing. .” Euro-Par (3) 2025: 48-62, 2025.","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} }","mla":"Scheideler, Christian, et al. <i>Supervised Distributed Computing. </i>. 2025.","short":"C. Scheideler, J. Augustine , J. Werthmann, in: Euro-Par (3) 2025: 48-62, 2025.","apa":"Scheideler, C., Augustine , J., &#38; Werthmann, J. (2025). <i>Supervised Distributed Computing. </i>."},"place":"Euro-Par (3) 2025: 48-62","year":"2025","title":"Supervised Distributed Computing. ","date_created":"2026-02-10T09:04:56Z","author":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"},{"first_name":"John ","full_name":"Augustine , John ","last_name":"Augustine "},{"last_name":"Werthmann","id":"50024","full_name":"Werthmann, Julian","first_name":"Julian"}],"date_updated":"2026-02-11T09:11:35Z"},{"publication_status":"published","publication_identifier":{"isbn":["9783031998713","9783031998720"],"issn":["0302-9743","1611-3349"]},"place":"Cham","year":"2025","citation":{"short":"J. Augustine, C. Scheideler, J. Werthmann, in: Lecture Notes in Computer Science, Springer Nature Switzerland, Cham, 2025.","mla":"Augustine, John, et al. “Supervised Distributed Computing.” <i>Lecture Notes in Computer Science</i>, Springer Nature Switzerland, 2025, doi:<a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">10.1007/978-3-031-99872-0_4</a>.","bibtex":"@inproceedings{Augustine_Scheideler_Werthmann_2025, place={Cham}, title={Supervised Distributed Computing}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">10.1007/978-3-031-99872-0_4</a>}, booktitle={Lecture Notes in Computer Science}, publisher={Springer Nature Switzerland}, author={Augustine, John and Scheideler, Christian and Werthmann, Julian}, year={2025} }","apa":"Augustine, J., Scheideler, C., &#38; Werthmann, J. (2025). Supervised Distributed Computing. <i>Lecture Notes in Computer Science</i>. <a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">https://doi.org/10.1007/978-3-031-99872-0_4</a>","chicago":"Augustine, John, Christian Scheideler, and Julian Werthmann. “Supervised Distributed Computing.” In <i>Lecture Notes in Computer Science</i>. Cham: Springer Nature Switzerland, 2025. <a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">https://doi.org/10.1007/978-3-031-99872-0_4</a>.","ieee":"J. Augustine, C. Scheideler, and J. Werthmann, “Supervised Distributed Computing,” 2025, doi: <a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">10.1007/978-3-031-99872-0_4</a>.","ama":"Augustine J, Scheideler C, Werthmann J. Supervised Distributed Computing. In: <i>Lecture Notes in Computer Science</i>. Springer Nature Switzerland; 2025. doi:<a href=\"https://doi.org/10.1007/978-3-031-99872-0_4\">10.1007/978-3-031-99872-0_4</a>"},"publisher":"Springer Nature Switzerland","date_updated":"2025-09-11T08:33:27Z","date_created":"2025-09-11T08:30:57Z","author":[{"first_name":"John","full_name":"Augustine, John","last_name":"Augustine"},{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"full_name":"Werthmann, Julian","id":"50024","last_name":"Werthmann","first_name":"Julian"}],"title":"Supervised Distributed Computing","doi":"10.1007/978-3-031-99872-0_4","type":"conference","publication":"Lecture Notes in Computer Science","status":"public","_id":"61184","user_id":"50024","language":[{"iso":"eng"}]},{"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-361-4"]},"year":"2025","place":"Dagstuhl, Germany","intvolume":"       325","page":"45:1–45:26","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. <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>. Vol 325. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2025:45:1–45:26. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>","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 <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, 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. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">https://doi.org/10.4230/LIPIcs.ITCS.2025.45</a>.","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 <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, 2025, vol. 325, p. 45:1–45:26, doi: <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>.","apa":"Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., &#38; Werthmann, J. (2025). Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In R. Meka (Ed.), <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i> (Vol. 325, p. 45:1–45:26). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">https://doi.org/10.4230/LIPIcs.ITCS.2025.45</a>","mla":"Dou, Jinfeng, et al. “Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs.” <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, edited by Raghu Meka, vol. 325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, p. 45:1–45:26, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>.","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={<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>}, 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)} }","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_updated":"2025-10-15T12:57:11Z","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","volume":325,"author":[{"first_name":"Jinfeng","last_name":"Dou","id":"92888","full_name":"Dou, Jinfeng"},{"last_name":"Götte","full_name":"Götte, Thorsten","id":"34727","first_name":"Thorsten"},{"first_name":"Henning","id":"74425","full_name":"Hillebrandt, Henning","last_name":"Hillebrandt"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"id":"50024","full_name":"Werthmann, Julian","last_name":"Werthmann","first_name":"Julian"}],"date_created":"2025-04-02T14:09:19Z","title":"Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs","doi":"10.4230/LIPIcs.ITCS.2025.45","publication":"16th Innovations in Theoretical Computer Science Conference (ITCS 2025)","type":"conference","editor":[{"first_name":"Raghu","full_name":"Meka, Raghu","last_name":"Meka"}],"status":"public","_id":"59268","user_id":"34727","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","language":[{"iso":"eng"}]},{"status":"public","publication":"Theoretical Computer Science","type":"journal_article","article_number":"115552","language":[{"iso":"eng"}],"_id":"62051","department":[{"_id":"79"}],"user_id":"55557","year":"2025","intvolume":"      1057","citation":{"ieee":"K. Hinnenthal, D. J. Liedtke, and C. Scheideler, “Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures,” <i>Theoretical Computer Science</i>, vol. 1057, Art. no. 115552, 2025, doi: <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>.","chicago":"Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>Theoretical Computer Science</i> 1057 (2025). <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">https://doi.org/10.1016/j.tcs.2025.115552</a>.","ama":"Hinnenthal K, Liedtke DJ, Scheideler C. Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures. <i>Theoretical Computer Science</i>. 2025;1057. doi:<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>","apa":"Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2025). Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures. <i>Theoretical Computer Science</i>, <i>1057</i>, Article 115552. <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">https://doi.org/10.1016/j.tcs.2025.115552</a>","mla":"Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>Theoretical Computer Science</i>, vol. 1057, 115552, Elsevier BV, 2025, doi:<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>.","short":"K. Hinnenthal, D.J. Liedtke, C. Scheideler, Theoretical Computer Science 1057 (2025).","bibtex":"@article{Hinnenthal_Liedtke_Scheideler_2025, title={Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures}, volume={1057}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>}, number={115552}, journal={Theoretical Computer Science}, publisher={Elsevier BV}, author={Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian}, year={2025} }"},"publication_identifier":{"issn":["0304-3975"]},"publication_status":"published","title":"Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures","doi":"10.1016/j.tcs.2025.115552","date_updated":"2025-11-03T10:21:52Z","publisher":"Elsevier BV","volume":1057,"date_created":"2025-11-03T10:19:53Z","author":[{"first_name":"Kristian","id":"32229","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal"},{"first_name":"David Jan","last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557"},{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"}]},{"publication":"3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)","type":"conference","editor":[{"full_name":"Casteigts, Arnaud","last_name":"Casteigts","first_name":"Arnaud"},{"first_name":"Fabian","last_name":"Kuhn","full_name":"Kuhn, Fabian"}],"abstract":[{"text":"This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pick-up, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an icicle. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in 𝒪(n³) steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average.","lang":"eng"}],"status":"public","_id":"54807","department":[{"_id":"79"}],"user_id":"55557","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","keyword":["Programmable Matter","Shape Formation","3D Model","Finite Automaton"],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-315-7"]},"year":"2024","place":"Dagstuhl, Germany","page":"15:1–15:20","intvolume":"       292","citation":{"chicago":"Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” In <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, edited by Arnaud Casteigts and Fabian Kuhn, 292:15:1–15:20. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>.","ieee":"K. Hinnenthal, D. J. Liedtke, and C. Scheideler, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures,” in <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, 2024, vol. 292, p. 15:1–15:20, doi: <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>.","ama":"Hinnenthal K, Liedtke DJ, Scheideler C. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In: Casteigts A, Kuhn F, eds. <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>. Vol 292. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2024:15:1–15:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>","apa":"Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2024). Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In A. Casteigts &#38; F. Kuhn (Eds.), <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i> (Vol. 292, p. 15:1–15:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>","bibtex":"@inproceedings{Hinnenthal_Liedtke_Scheideler_2024, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures}, volume={292}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>}, booktitle={3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={15:1–15:20}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"K. Hinnenthal, D.J. Liedtke, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024, p. 15:1–15:20.","mla":"Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 15:1–15:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>."},"date_updated":"2024-07-18T09:32:49Z","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","volume":292,"author":[{"full_name":"Hinnenthal, Kristian","id":"32229","last_name":"Hinnenthal","first_name":"Kristian"},{"last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan","first_name":"David Jan"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"}],"date_created":"2024-06-18T07:45:34Z","title":"Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures","doi":"10.4230/LIPIcs.SAND.2024.15"},{"publication_identifier":{"isbn":["9783031606021","9783031606038"],"issn":["0302-9743","1611-3349"]},"publication_status":"published","citation":{"apa":"Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2024). Universal Coating by 3D Hybrid Programmable Matter. In Y. Emek (Ed.), <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>","short":"I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: Y. Emek (Ed.), Structural Information and Communication Complexity, Springer Nature Switzerland, Cham, 2024.","bibtex":"@inbook{Kostitsyna_Liedtke_Scheideler_2024, place={Cham}, title={Universal Coating by 3D Hybrid Programmable Matter}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>}, booktitle={Structural Information and Communication Complexity}, publisher={Springer Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}, editor={Emek, Yuval}, year={2024} }","mla":"Kostitsyna, Irina, et al. “Universal Coating by 3D Hybrid Programmable Matter.” <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek, Springer Nature Switzerland, 2024, doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>.","ama":"Kostitsyna I, Liedtke DJ, Scheideler C. Universal Coating by 3D Hybrid Programmable Matter. In: Emek Y, ed. <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland; 2024. doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>","ieee":"I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Universal Coating by 3D Hybrid Programmable Matter,” in <i>Structural Information and Communication Complexity</i>, Y. Emek, Ed. Cham: Springer Nature Switzerland, 2024.","chicago":"Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Universal Coating by 3D Hybrid Programmable Matter.” In <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek. Cham: Springer Nature Switzerland, 2024. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>."},"place":"Cham","year":"2024","date_created":"2024-06-18T07:36:04Z","author":[{"first_name":"Irina","last_name":"Kostitsyna","full_name":"Kostitsyna, Irina"},{"first_name":"David Jan","full_name":"Liedtke, David Jan","id":"55557","last_name":"Liedtke"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"publisher":"Springer Nature Switzerland","date_updated":"2024-07-18T09:32:58Z","doi":"10.1007/978-3-031-60603-8_21","title":"Universal Coating by 3D Hybrid Programmable Matter","publication":"Structural Information and Communication Complexity","type":"book_chapter","status":"public","abstract":[{"text":"Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid programmable matter. In this model, a single agent with strictly limited viewing range and the computational capability of a deterministic finite automaton can act on passive tiles by picking up a tile, moving, and placing it at some spot. The goal of the coating problem is to fill each node of some surface graph of size n with a tile. We first solve the problem on a restricted class of graphs with a single tile type, and then use constantly many tile types to encode this graph in certain surface graphs capturing the surface of 3D objects. Our algorithm requires O(n^2) steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions.","lang":"eng"}],"editor":[{"full_name":"Emek, Yuval","last_name":"Emek","first_name":"Yuval"}],"department":[{"_id":"79"}],"user_id":"55557","_id":"54802","language":[{"iso":"eng"}],"keyword":["Programmable Matter","Coating","Finite Automaton","3D"]},{"citation":{"ieee":"A. Padalkin, C. Scheideler, and D. Warner, “The structural power of reconfigurable circuits in the amoebot model,” <i>Natural Computing</i>, 2024, doi: <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>.","chicago":"Padalkin, Andreas, Christian Scheideler, and Daniel Warner. “The Structural Power of Reconfigurable Circuits in the Amoebot Model.” <i>Natural Computing</i>, 2024. <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">https://doi.org/10.1007/s11047-024-09981-6</a>.","ama":"Padalkin A, Scheideler C, Warner D. The structural power of reconfigurable circuits in the amoebot model. <i>Natural Computing</i>. Published online 2024. doi:<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>","short":"A. Padalkin, C. Scheideler, D. Warner, Natural Computing (2024).","bibtex":"@article{Padalkin_Scheideler_Warner_2024, title={The structural power of reconfigurable circuits in the amoebot model}, DOI={<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>}, journal={Natural Computing}, publisher={Springer Science and Business Media LLC}, author={Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}, year={2024} }","mla":"Padalkin, Andreas, et al. “The Structural Power of Reconfigurable Circuits in the Amoebot Model.” <i>Natural Computing</i>, Springer Science and Business Media LLC, 2024, doi:<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>.","apa":"Padalkin, A., Scheideler, C., &#38; Warner, D. (2024). The structural power of reconfigurable circuits in the amoebot model. <i>Natural Computing</i>. <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">https://doi.org/10.1007/s11047-024-09981-6</a>"},"year":"2024","publication_identifier":{"issn":["1567-7818","1572-9796"]},"publication_status":"published","doi":"10.1007/s11047-024-09981-6","title":"The structural power of reconfigurable circuits in the amoebot model","date_created":"2024-07-24T14:28:27Z","author":[{"last_name":"Padalkin","id":"88238","full_name":"Padalkin, Andreas","first_name":"Andreas"},{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"last_name":"Warner","full_name":"Warner, Daniel","id":"3902","first_name":"Daniel"}],"date_updated":"2024-07-24T14:28:43Z","publisher":"Springer Science and Business Media LLC","status":"public","abstract":[{"text":"<jats:title>Abstract</jats:title><jats:p>The <jats:italic>amoebot model</jats:italic> (Derakhshandeh et al. in: SPAA ACM, pp 220–222. <jats:ext-link xmlns:xlink=\"http://www.w3.org/1999/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1145/2612669.2612712\">https://doi.org/10.1145/2612669.2612712</jats:ext-link>, 2014) has been proposed as a model for programmable matter consisting of tiny, robotic elements called <jats:italic>amoebots</jats:italic>. We consider the <jats:italic>reconfigurable circuit extension</jats:italic> (Feldmann et al. in J Comput Biol 29(4):317–343. <jats:ext-link xmlns:xlink=\"http://www.w3.org/1999/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1089/cmb.2021.0363\">https://doi.org/10.1089/cmb.2021.0363</jats:ext-link>, 2022) of the geometric amoebot model that allows the amoebot structure to interconnect amoebots by so-called <jats:italic>circuits</jats:italic>. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with fundamental problems like the <jats:italic>stripe computation problem</jats:italic> where, given any connected amoebot structure <jats:italic>S</jats:italic>, an amoebot <jats:italic>u</jats:italic> in <jats:italic>S</jats:italic>, and some axis <jats:italic>X</jats:italic>, all amoebots belonging to axis <jats:italic>X</jats:italic> through <jats:italic>u</jats:italic> have to be identified. Second, we consider the <jats:italic>global maximum problem</jats:italic>, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can be used to solve the <jats:italic>skeleton problem</jats:italic>, where a cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions allows the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.</jats:p>","lang":"eng"}],"publication":"Natural Computing","type":"journal_article","language":[{"iso":"eng"}],"user_id":"88238","_id":"55379"},{"year":"2024","citation":{"apa":"Padalkin, A., Kumar, M., &#38; Scheideler, C. (2024). Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In A. Casteigts &#38; F. Kuhn (Eds.), <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i> (Vol. 292, p. 18:1–18:20). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">https://doi.org/10.4230/LIPICS.SAND.2024.18</a>","mla":"Padalkin, Andreas, et al. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model.” <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1–18:20, doi:<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>.","bibtex":"@inproceedings{Padalkin_Kumar_Scheideler_2024, series={LIPIcs}, title={Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}, volume={292}, DOI={<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>}, booktitle={3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={Padalkin, Andreas and Kumar, Manish and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={18:1–18:20}, collection={LIPIcs} }","short":"A. Padalkin, M. Kumar, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1–18:20.","ama":"Padalkin A, Kumar M, Scheideler C. Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In: Casteigts A, Kuhn F, eds. <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>. Vol 292. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:18:1–18:20. doi:<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>","chicago":"Padalkin, Andreas, Manish Kumar, and Christian Scheideler. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model.” In <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, edited by Arnaud Casteigts and Fabian Kuhn, 292:18:1–18:20. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">https://doi.org/10.4230/LIPICS.SAND.2024.18</a>.","ieee":"A. Padalkin, M. Kumar, and C. Scheideler, “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model,” in <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, 2024, vol. 292, p. 18:1–18:20, doi: <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>."},"intvolume":"       292","page":"18:1–18:20","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2024-07-24T14:25:46Z","author":[{"first_name":"Andreas","last_name":"Padalkin","full_name":"Padalkin, Andreas","id":"88238"},{"first_name":"Manish","last_name":"Kumar","full_name":"Kumar, Manish"},{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"}],"date_created":"2024-07-24T14:25:07Z","volume":292,"title":"Reconfiguration and Locomotion with Joint Movements in the Amoebot Model","doi":"10.4230/LIPICS.SAND.2024.18","type":"conference","publication":"3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece","editor":[{"last_name":"Casteigts","full_name":"Casteigts, Arnaud","first_name":"Arnaud"},{"first_name":"Fabian","last_name":"Kuhn","full_name":"Kuhn, Fabian"}],"status":"public","_id":"55376","user_id":"88238","series_title":"LIPIcs","language":[{"iso":"eng"}]},{"publication":"Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing","type":"conference","status":"public","_id":"55377","user_id":"88238","language":[{"iso":"eng"}],"publication_status":"published","year":"2024","citation":{"chicago":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” In <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. ACM, 2024. <a href=\"https://doi.org/10.1145/3662158.3662776\">https://doi.org/10.1145/3662158.3662776</a>.","ieee":"A. Padalkin and C. Scheideler, “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter,” 2024, doi: <a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>.","ama":"Padalkin A, Scheideler C. Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. In: <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. ACM; 2024. doi:<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>","mla":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>, ACM, 2024, doi:<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>.","bibtex":"@inproceedings{Padalkin_Scheideler_2024, title={Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter}, DOI={<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>}, booktitle={Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing}, publisher={ACM}, author={Padalkin, Andreas and Scheideler, Christian}, year={2024} }","short":"A. Padalkin, C. Scheideler, in: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, ACM, 2024.","apa":"Padalkin, A., &#38; Scheideler, C. (2024). Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. <a href=\"https://doi.org/10.1145/3662158.3662776\">https://doi.org/10.1145/3662158.3662776</a>"},"date_updated":"2024-07-24T14:26:23Z","publisher":"ACM","date_created":"2024-07-24T14:26:10Z","author":[{"id":"88238","full_name":"Padalkin, Andreas","last_name":"Padalkin","first_name":"Andreas"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"}],"title":"Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter","doi":"10.1145/3662158.3662776"},{"author":[{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"first_name":"Kristian ","last_name":"Hinnenthal ","full_name":"Hinnenthal , Kristian "},{"last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557","first_name":"David Jan"}],"date_created":"2026-02-10T10:12:18Z","date_updated":"2026-02-11T09:12:05Z","title":"Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20","citation":{"mla":"Scheideler, Christian, et al. <i>Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20</i>. 2024.","bibtex":"@inproceedings{Scheideler_Hinnenthal _Liedtke_2024, place={CoRR abs/2401.17734 (2024)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20}, author={Scheideler, Christian and Hinnenthal , Kristian  and Liedtke, David Jan}, year={2024} }","short":"C. Scheideler, K. Hinnenthal , D.J. Liedtke, in: CoRR abs/2401.17734 (2024), 2024.","apa":"Scheideler, C., Hinnenthal , K., &#38; Liedtke, D. J. (2024). <i>Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20</i>.","ieee":"C. Scheideler, K. Hinnenthal , and D. J. Liedtke, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20,” 2024.","chicago":"Scheideler, Christian, Kristian  Hinnenthal , and David Jan Liedtke. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20.” CoRR abs/2401.17734 (2024), 2024.","ama":"Scheideler C, Hinnenthal  K, Liedtke DJ. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20. In: ; 2024."},"year":"2024","place":"CoRR abs/2401.17734 (2024)","user_id":"15578","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"_id":"64104","language":[{"iso":"eng"}],"type":"conference","status":"public"},{"type":"conference","status":"public","_id":"64103","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","language":[{"iso":"eng"}],"year":"2024","place":"PODC 2024: 65-75","page":"65 - 75","citation":{"apa":"Scheideler, C., &#38; Padalkin, A. (2024). <i>Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. </i>. 65–75.","bibtex":"@inproceedings{Scheideler_Padalkin_2024, place={PODC 2024: 65-75}, title={Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. }, author={Scheideler, Christian and Padalkin, Andreas}, year={2024}, pages={65–75} }","mla":"Scheideler, Christian, and Andreas Padalkin. <i>Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. </i>. 2024, pp. 65–75.","short":"C. Scheideler, A. Padalkin, in: PODC 2024: 65-75, 2024, pp. 65–75.","ieee":"C. Scheideler and A. Padalkin, “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. ,” 2024, pp. 65–75.","chicago":"Scheideler, Christian, and Andreas Padalkin. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. ,” 65–75. PODC 2024: 65-75, 2024.","ama":"Scheideler C, Padalkin A. Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. . In: ; 2024:65-75."},"date_updated":"2026-02-11T09:11:58Z","author":[{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"},{"last_name":"Padalkin","id":"88238","full_name":"Padalkin, Andreas","first_name":"Andreas"}],"date_created":"2026-02-10T10:06:36Z","title":"Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. "},{"type":"conference","status":"public","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","_id":"64106","language":[{"iso":"eng"}],"citation":{"ama":"Scheideler C, Kostitsyna I, Liedtke DJ. Universal Coating by 3D Hybrid Programmable Matter. In: ; 2024.","chicago":"Scheideler, Christian, Irina  Kostitsyna, and David Jan Liedtke. “Universal Coating by 3D Hybrid Programmable Matter.” SIROCCO 2024: 384-401, 2024.","ieee":"C. Scheideler, I. Kostitsyna, and D. J. Liedtke, “Universal Coating by 3D Hybrid Programmable Matter.,” 2024.","mla":"Scheideler, Christian, et al. <i>Universal Coating by 3D Hybrid Programmable Matter.</i> 2024.","bibtex":"@inproceedings{Scheideler_Kostitsyna_Liedtke_2024, place={SIROCCO 2024: 384-401}, title={Universal Coating by 3D Hybrid Programmable Matter.}, author={Scheideler, Christian and Kostitsyna, Irina  and Liedtke, David Jan}, year={2024} }","short":"C. Scheideler, I. Kostitsyna, D.J. Liedtke, in: SIROCCO 2024: 384-401, 2024.","apa":"Scheideler, C., Kostitsyna, I., &#38; Liedtke, D. J. (2024). <i>Universal Coating by 3D Hybrid Programmable Matter.</i>"},"year":"2024","place":"SIROCCO 2024: 384-401","date_created":"2026-02-10T10:21:39Z","author":[{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"},{"first_name":"Irina ","full_name":"Kostitsyna, Irina ","last_name":"Kostitsyna"},{"last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan","first_name":"David Jan"}],"date_updated":"2026-02-11T09:12:11Z","title":"Universal Coating by 3D Hybrid Programmable Matter."},{"status":"public","publication":"The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4): 603-625 (2024)","type":"journal_article","language":[{"iso":"eng"}],"department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","_id":"64100","page":"603 - 625","citation":{"chicago":"Scheideler, Christian, Andreas Padalkin, and Daniel Warner. “The Structural Power of Reconfigurable Circuits in the Amoebot Model. .” <i>The Structural Power of Reconfigurable Circuits in the Amoebot Model. Nat. Comput. 23(4): 603-625 (2024)</i>, 2024, 603–25.","ieee":"C. Scheideler, A. Padalkin, and D. Warner, “The structural power of reconfigurable circuits in the amoebot model. ,” <i>The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4): 603-625 (2024)</i>, pp. 603–625, 2024.","ama":"Scheideler C, Padalkin A, Warner D. The structural power of reconfigurable circuits in the amoebot model. . <i>The structural power of reconfigurable circuits in the amoebot model Nat Comput 23(4): 603-625 (2024)</i>. Published online 2024:603-625.","apa":"Scheideler, C., Padalkin, A., &#38; Warner, D. (2024). The structural power of reconfigurable circuits in the amoebot model. . <i>The Structural Power of Reconfigurable Circuits in the Amoebot Model. Nat. Comput. 23(4): 603-625 (2024)</i>, 603–625.","bibtex":"@article{Scheideler_Padalkin_Warner_2024, title={The structural power of reconfigurable circuits in the amoebot model. }, journal={The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4): 603-625 (2024)}, author={Scheideler, Christian and Padalkin, Andreas and Warner, Daniel}, year={2024}, pages={603–625} }","short":"C. Scheideler, A. Padalkin, D. Warner, The Structural Power of Reconfigurable Circuits in the Amoebot Model. Nat. Comput. 23(4): 603-625 (2024) (2024) 603–625.","mla":"Scheideler, Christian, et al. “The Structural Power of Reconfigurable Circuits in the Amoebot Model. .” <i>The Structural Power of Reconfigurable Circuits in the Amoebot Model. Nat. Comput. 23(4): 603-625 (2024)</i>, 2024, pp. 603–25."},"year":"2024","title":"The structural power of reconfigurable circuits in the amoebot model. ","author":[{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Andreas","full_name":"Padalkin, Andreas","id":"88238","last_name":"Padalkin"},{"first_name":"Daniel","last_name":"Warner","full_name":"Warner, Daniel","id":"3902"}],"date_created":"2026-02-10T09:56:23Z","date_updated":"2026-02-11T09:13:04Z"},{"author":[{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"last_name":"Coy","full_name":"Coy, Sam ","first_name":"Sam "},{"full_name":"Czumaj, Arthur ","last_name":"Czumaj","first_name":"Arthur "},{"full_name":"Schneider, Philipp ","last_name":"Schneider","first_name":"Philipp "},{"last_name":"Werthmann","full_name":"Werthmann, Julian","id":"50024","first_name":"Julian"}],"date_created":"2026-02-10T10:00:43Z","date_updated":"2026-02-11T09:12:57Z","title":"Routing schemes for hybrid communication networks. ","citation":{"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} }","short":"C. Scheideler, S. Coy, A. Czumaj, P. Schneider, J. Werthmann, Routing Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024) (2024).","mla":"Scheideler, Christian, et al. “Routing Schemes for Hybrid Communication Networks. .” <i>Routing Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024)</i>, 2024.","apa":"Scheideler, C., Coy, S., Czumaj, A., Schneider, P., &#38; Werthmann, J. (2024). Routing schemes for hybrid communication networks. . <i>Routing Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024)</i>.","ama":"Scheideler C, Coy S, Czumaj A, Schneider P, Werthmann J. Routing schemes for hybrid communication networks. . <i>Routing schemes for hybrid communication networks Theor Comput Sci 985: 114352 (2024)</i>. Published online 2024.","chicago":"Scheideler, Christian, Sam  Coy, Arthur  Czumaj, Philipp  Schneider, and Julian Werthmann. “Routing Schemes for Hybrid Communication Networks. .” <i>Routing Schemes for Hybrid Communication Networks. Theor. Comput. Sci. 985: 114352 (2024)</i>, 2024.","ieee":"C. Scheideler, S. Coy, A. Czumaj, P. Schneider, and J. Werthmann, “Routing schemes for hybrid communication networks. ,” <i>Routing schemes for hybrid communication networks. Theor. Comput. Sci. 985: 114352 (2024)</i>, 2024."},"year":"2024","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","_id":"64101","language":[{"iso":"eng"}],"publication":"Routing schemes for hybrid communication networks. Theor. Comput. Sci. 985: 114352 (2024)","type":"journal_article","status":"public"}]