---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Zuzana
foaf_name: Masárová, Zuzana
foaf_surname: Masárová
foaf_workInfoHomepage: http://www.librecat.org/personId=45CFE238-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-6660-1322
bibo_doi: 10.15479/AT:ISTA:7944
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2663-337X
- http://id.crossref.org/issn/978-3-99078-005-3
dct_language: eng
dct_publisher: Institute of Science and Technology Austria@
dct_subject:
- reconfiguration
- reconfiguration graph
- triangulations
- flip
- constrained triangulations
- shellability
- piecewise-linear balls
- token swapping
- trees
- coloured weighted token swapping
dct_title: Reconfiguration problems@
...