---
_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:<a href="https://doi.org/10.15479/AT:ISTA:7944">10.15479/AT:ISTA:7944</a>
  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>
  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>.
  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. <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.
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'
...