Computing Optimal Tangles Faster

01/19/2019
by   Oksana Firman, et al.
0

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φ^n n) time, where φ≈ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset