Implicit computation of minimum-cost feedback-vertex sets for partial scan and other applications

Pranav Ashar, Sharad Malik

Research output: Contribution to journalConference article

25 Scopus citations

Abstract

The contribution of this paper is an implicit method for computing the minimum cost feedback vertex set for a graph. For an arbitrary graph, we efficiently derive a Boolean function whose satisfying assignments directly correspond to feedback vertex sets of the graph. Importantly, cycles in the graph are never explicitly enumerated, but rather, are captured implicitly in this Boolean function. This function is then used to determine the minimum cost feedback vertex set. Even though computing the minimum cost satisfying assignment for a Boolean function remains an NP-hard problem, we can exploit the advances made in the area of Boolean function representation in logic synthesis to tackle this problem efficiently in practice for even reasonably large sized graphs. The algorithm has obvious application in flip-flop selection for partial scan. Our algorithm was the first to obtain the MFVS solutions for many benchmark circuits.

Original languageEnglish (US)
Pages (from-to)77-80
Number of pages4
JournalProceedings - Design Automation Conference
DOIs
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the 31st Design Automation Conference - San Diego, CA, USA
Duration: Jun 6 1994Jun 10 1994

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Implicit computation of minimum-cost feedback-vertex sets for partial scan and other applications'. Together they form a unique fingerprint.

  • Cite this