Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching instances proposed by the authors in a previous paper. We present computational results for both random and real-world instances having between 1,000 and 131,072 vertices. The results indicate that our algorithm generates a matching within 2% of optimal in most cases. In over 1,400 experiments, the algorithm was never more than 4% from optimal. For the purposes of the study, we give a new implementation of the algorithm that uses linear space instead of quadratic space, and appears to run faster in practice. © 1996 INFORMS.
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Michael D. Moffitt
ICCAD 2009