[{"citation":{"ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>.","mla":"Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>.","short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","apa":"Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>","ama":"Masárová Z. Reconfiguration problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>"},"title":"Reconfiguration problems","day":"09","type":"dissertation","author":[{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana"}],"alternative_title":["ISTA Thesis"],"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"7950"},{"status":"public","id":"5986","relation":"part_of_dissertation"}]},"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"language":[{"iso":"eng"}],"doi":"10.15479/AT:ISTA:7944","ddc":["516","514"],"page":"160","month":"06","supervisor":[{"last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"},{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"}],"date_created":"2020-06-08T00:49:46Z","publisher":"Institute of Science and Technology Austria","degree_awarded":"PhD","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","year":"2020","oa_version":"Published Version","date_updated":"2023-09-07T13:17:37Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"article_processing_charge":"No","file":[{"access_level":"open_access","date_updated":"2020-07-14T12:48:05Z","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","file_size":13661779,"creator":"zmasarov","file_name":"THESIS_Zuzka_Masarova.pdf","date_created":"2020-06-08T00:34:00Z","relation":"main_file","file_id":"7945","content_type":"application/pdf"},{"file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","file_size":32184006,"creator":"zmasarov","checksum":"45341a35b8f5529c74010b7af43ac188","date_updated":"2020-07-14T12:48:05Z","access_level":"closed","content_type":"application/zip","file_id":"7946","relation":"source_file","date_created":"2020-06-08T00:35:30Z"}],"date_published":"2020-06-09T00:00:00Z","_id":"7944","abstract":[{"text":"This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.","lang":"eng"}],"publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:48:05Z","tmp":{"short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode"}},{"date_updated":"2023-09-07T13:18:26Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1812.05528"]},"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"has_accepted_license":"1","oa_version":"Published Version","year":"2019","file_date_updated":"2020-07-14T12:47:33Z","volume":129,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_status":"published","oa":1,"file":[{"file_name":"2019_LIPIcs-Huszar.pdf","creator":"kschuh","file_size":905885,"checksum":"29d18c435368468aa85823dabb157e43","date_updated":"2020-07-14T12:47:33Z","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_id":"6557","date_created":"2019-06-12T06:45:33Z"}],"_id":"6556","abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"date_published":"2019-06-01T00:00:00Z","arxiv":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"doi":"10.4230/LIPIcs.SoCG.2019.44","ddc":["516"],"related_material":{"record":[{"id":"8032","relation":"part_of_dissertation","status":"public"}]},"day":"01","alternative_title":["LIPIcs"],"author":[{"last_name":"Huszár","full_name":"Huszár, Kristóf","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"}],"type":"conference","citation":{"short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","apa":"Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In <i>35th International Symposium on Computational Geometry</i>, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>."},"conference":{"end_date":"2019-06-21","start_date":"2019-06-18","name":"SoCG: Symposium on Computational Geometry","location":"Portland, Oregon, United States"},"title":"3-manifold triangulations with small treewidth","department":[{"_id":"UlWa"}],"quality_controlled":"1","publication":"35th International Symposium on Computational Geometry","status":"public","intvolume":"       129","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"06","date_created":"2019-06-11T20:09:57Z","page":"44:1-44:20"}]