Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
We consider the problem of finding a maximum subset of a given set of wires connecting two rows of terminals with fixed positions, such that no wires in the subset cross. We derive an algorithm that runs in O(p + (n - p) ℓ g(p + 1)) time, where n is the number of wires given and p is the maximum number of noncrossing wires; in many practically relevant cases, e.g., when p is very high, it needs only linear time. We show how an extension of the algorithm solves the more general problem, where the positions of some terminals have some flexibility, within the same time bound. © 1985.
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB