Finding Maximum Noncrossing Subset of Nets Using Longest Increasing Subsequence

摘要

In the problem of maximum noncrossing subset of nets, the current algorithms of using either dynamic programming or the longest common subsequence have the complexity of O(n2). In order to reduce the complexity of the existing algorithms, a more efficient algorithm of using longest increasing subsequence is introduced in this paper. The effectiveness of the algorithm with a time consuming complexity of O(nlogn) is illustrated through the theoretical analysis and by demonstrating the experiment results of corresponding C++ program.