Comment on “On Optimal Hyperuniversal and Rearrangeable Switch Box Designs”

摘要

Fan proposed a set of hyperuniversal switch blocks (HUSBs), called Fan’s (4, )-HUSBs in this paper. He also proved that his design with less than 6 was optimum. That is, they used the least switches to achieve hyperuniversal routability. However, we find a counter example to show that there is an unnecessary switch in Fan’s (4, 4)-HUSB. Namely, we propose a new (4, 4)-HUSB, water-molecule-shaped switch block (WMSB), proving (4, 4)-WMSB with 24 switches is optimal. Furthermore, we also propose optimal (4, 7)-WMSB, which is a (4, 7)-HUSB with 42 switches.