Maximum weighted independent sets on transitive graphs and applications

We present a polynomial-time algorithm that finds the maximum weighted inde pendent set of a transitive graph. The studied problem finds applications i n a variety of VLSI contexts, including path delay fault testing, schedulin g in high-level synthesis, and channel routing in physical design automatio n. The algorithm has been implemented and incorporated in a CAD tool for pa th delay fault testing. We experimentally verify its impact in the latter c ontext. (C) 1999 Published by Elsevier Science B.V. All rights reserved.