Maximum weighted independent sets on transitive graphs and applications
We present a polynomial-time algorithm that finds the maximum weighted independent set of a transitive graph. The studied problem finds applications in a variety of VLSI contexts, including path delay fault testing, scheduling in high-level synthesis, and channel routing in physical design automation. The algorithm has been implemented and incorporated in a CAD tool for path delay fault testing. We experimentally verify its impact in the latter context. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
maximum weighted independent sets high-level synthesis channel routing delay testing