Linear optimal one-sided single-detour algorithm for untangling twisted bus

We considered the one-sided single-detour untangling twisted nets problem for printed circuit board bus routing. A previous optimal dynamic programming based O(n 3 ) algorithm was proposed in a previous work, where n is the number of nets. In this paper, we propose an optimal O(n) untangling algorithm without considering capacity, and this algorithm is further modified to consider capacity. Experimental results show that our algorithms runs much faster than the previous work due to its low time complexity.