---
_id: '7944'
abstract:
- lang: eng
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."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
citation:
ama: Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944
apa: Masárová, Z. (2020). *Reconfiguration problems*. Institute of Science
and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944
chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and
Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.
ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology
Austria, 2020.
ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology
Austria.
mla: Masárová, Zuzana. *Reconfiguration Problems*. Institute of Science and
Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.
short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology
Austria, 2020.
date_created: 2020-06-08T00:49:46Z
date_published: 2020-06-09T00:00:00Z
date_updated: 2023-09-07T13:17:37Z
day: '09'
ddc:
- '516'
- '514'
degree_awarded: PhD
department:
- _id: HeEd
- _id: UlWa
doi: 10.15479/AT:ISTA:7944
file:
- access_level: open_access
checksum: df688bc5a82b50baee0b99d25fc7b7f0
content_type: application/pdf
creator: zmasarov
date_created: 2020-06-08T00:34:00Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7945'
file_name: THESIS_Zuzka_Masarova.pdf
file_size: 13661779
relation: main_file
- access_level: closed
checksum: 45341a35b8f5529c74010b7af43ac188
content_type: application/zip
creator: zmasarov
date_created: 2020-06-08T00:35:30Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7946'
file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip
file_size: 32184006
relation: source_file
file_date_updated: 2020-07-14T12:48:05Z
has_accepted_license: '1'
keyword:
- reconfiguration
- reconfiguration graph
- triangulations
- flip
- constrained triangulations
- shellability
- piecewise-linear balls
- token swapping
- trees
- coloured weighted token swapping
language:
- iso: eng
license: https://creativecommons.org/licenses/by-sa/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: '160'
publication_identifier:
isbn:
- 978-3-99078-005-3
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '7950'
relation: part_of_dissertation
status: public
- id: '5986'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
title: Reconfiguration problems
tmp:
image: /images/cc_by_sa.png
legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode
name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC
BY-SA 4.0)
short: CC BY-SA (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...