The complexity of generalized retiming problems

B.L.E. de Fluiter, E.H.L. Aarts, J.H.M. Korst, W.F.J. Verhaegh, A. Werf van der

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)


We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time
Original languageEnglish
Pages (from-to)1340-1353
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
Publication statusPublished - 1996
Externally publishedYes


Dive into the research topics of 'The complexity of generalized retiming problems'. Together they form a unique fingerprint.

Cite this