Circuit partitioning with size and connection constraints

DOI10.1002/net.3230130305zbMath0521.68035OpenAlexW2094911455MaRDI QIDQ3670554

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

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 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)

Related Items

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

Cites Work

• The art and theory of dynamic programming

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