Name
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}varphi^n n)$ time, where $varphi approx 1.618$ is the golden ratio. We can treat lists where every swap occurs at most once in $O(n!varphi^n)$ time. We implemented the algorithm for the general case and compared it to an existing algorithm. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Discrete Mathematics | Journal |
Volume | Citations | PageRank |
abs/1901.06548 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oksana Firman | 1 | 0 | 0.68 |
| Philipp Kindermann | 2 | 63 | 11.87 |
| Alexander Ravsky | 3 | 10 | 2.31 |
| Alexander Wolff | 4 | 222 | 22.66 |
| Johannes Zink | 5 | 0 | 1.01 |