Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1901.06548 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916076806209536 |
|---|---|
| author | Firman, Oksana Kindermann, Philipp Ravsky, Alexander Wolff, Alexander Zink, Johannes |
| author_facet | Firman, Oksana Kindermann, Philipp Ravsky, Alexander Wolff, Alexander Zink, Johannes |
| contents | 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} \cdot φ^n \cdot n)$ time, where $φ\approx 1.618$ is the golden ratio. We can treat lists where every swap occurs at most once in $O(n!φ^n)$ time. We implemented the algorithm for the general case and compared it to an existing algorithm. Finally, we discuss feasibility for lists with a simple structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_06548 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Computing Height-Optimal Tangles Faster Firman, Oksana Kindermann, Philipp Ravsky, Alexander Wolff, Alexander Zink, Johannes Discrete Mathematics 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} \cdot φ^n \cdot n)$ time, where $φ\approx 1.618$ is the golden ratio. We can treat lists where every swap occurs at most once in $O(n!φ^n)$ time. We implemented the algorithm for the general case and compared it to an existing algorithm. Finally, we discuss feasibility for lists with a simple structure. |
| title | Computing Height-Optimal Tangles Faster |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/1901.06548 |