%0 Conference Paper %1 fkrwz-cotf-eurocg19 %A Firman, Oksana %A Kindermann, Philipp %A Ravsky, Alexander %A Wolff, Alexander %A Zink, Johannes %B Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19) %D 2019 %E Löffler, Maarten %I Utrecht %K myown %T Computing Optimal Tangles Faster %U http://www.eurocg2019.uu.nl/papers/61.pdf %X We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

@inproceedings{fkrwz-cotf-eurocg19, abstract = {We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.}, added-at = {2019-10-01T18:14:41.000+0200}, arxiv = {https://arxiv.org/abs/1901.06548}, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/294f32bf9ee71c4eaecbe8b3b9e0d9141/kindermann}, booktitle = {Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19)}, editor = {Löffler, Maarten}, interhash = {ba2be558913ab887e047579b381e8712}, intrahash = {94f32bf9ee71c4eaecbe8b3b9e0d9141}, keywords = {myown}, note = {Abstract}, publisher = {Utrecht}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2019-gd-tangles-oksana.pdf}, timestamp = {2019-10-01T18:28:08.000+0200}, title = {Computing Optimal Tangles Faster}, url = {http://www.eurocg2019.uu.nl/papers/61.pdf}, year = 2019 }