Circuit partitioning with size and connection constraints

DOI10.1002/NET.3230130305zbMATH Open0521.68035OpenAlexW2094911455MaRDI QIDQ3670554FDOQ3670554

Marc Snir, Yehoshua Perl

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230130305

zbMATH Keywords

NP-completecircuit partitioningpseudo-polynomial dynamic programming algorithm

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)

Cites Work

• The art and theory of dynamic programming

Cited In (6)

• A shifting algorithm for constrained min-max partition on trees
• Best location of service centers in a treelike network under budget constraints
• Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
• The shifting algorithm technique for the partitioning of trees
• Most uniform path partitioning and its use in image processing
• An efficient ZK compiler from SIMD circuits to general circuits

This page was built for publication: Circuit partitioning with size and connection constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3670554)