Clustering without replication in combinatorial circuits

Zola Donovan (), Gregory Gutin (), Vahan Mkrtchyan () and K. Subramani ()
Additional contact information
Zola Donovan: West Virginia University
Gregory Gutin: Royal Holloway University of London
Vahan Mkrtchyan: West Virginia University
K. Subramani: West Virginia University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 9, 501 pages

Abstract: Abstract The modern integrated circuit is one of the most complex products engineered to date. It continues to grow in complexity as years progress. As a result, very large-scale integrated (VLSI) circuit design now involves massive design teams employing state-of-the-art computer-aided design (CAD) tools. One of the oldest, yet most important CAD problems for VLSI circuits is physical design automation, where one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface (Lim in Practical problems in VLSI physical design automation, Springer, Dordrecht, 2008). The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there exists several models for the clustering problem. In particular, we consider the problem of clustering in combinatorial circuits for delay minimization, without permitting logic replication (CN). The problem of clustering for delay minimization when logic replication is allowed (CA) has been well-studied and is known to be solvable in polynomial time (Lawler et al. in IEEE Trans Comput 18(1):47–57, 1969; Rajaraman and Wong, in: 30th ACM/IEEE design automation conference, pp 309–314, 1993). However, unbounded logic replication can be quite expensive. It follows that CN is an important problem. We show that selected variants of CN are NP-hard. We also obtain approximability and inapproximability results for some of these problems. A preliminary version of this paper appears in Donovan et al. (in: 9th International conference on combinatorial optimization and applications, COCOA 2015, Proceedings, pp 334–347, 2015).

Keywords: Clustering without replication; Computational complexity; NP-completeness; Approximation; Inapproximability (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00394-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00394-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00394-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().