Maximum weighted independent sets on transitive graphs and applications

Citation
D. Kagaris et S. Tragoudas, Maximum weighted independent sets on transitive graphs and applications, INTEGRATION, 27(1), 1999, pp. 77-86
Citations number
13
Categorie Soggetti
Computer Science & Engineering
Journal title
INTEGRATION-THE VLSI JOURNAL
ISSN journal
01679260 → ACNP
Volume
27
Issue
1
Year of publication
1999
Pages
77 - 86
Database
ISI
SICI code
0167-9260(199901)27:1<77:MWISOT>2.0.ZU;2-Q
Abstract
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.