On the complexity of some partition problems

MaRDI QIDQ1386936zbMATH OpenFDO

Authors L. N. Andreeva, A. M. Oranov

Publication date 8 November 1998

Published in Journal of Computer and Systems Sciences International (Search for Journal in Brave)

zbMATH Keywords

combinatorial circuitsNP-hardpartitioning finite setspolynomial subproblems

Mathematics Subject Classification ID

Partitions of sets (05A18) Analysis of algorithms and problem complexity (68Q25) Circuits, networks (94C99)

Recommendations

• Synthesis of discrete circuits in a PLD basis
• Computational complexity of the product partition problem
• ``NP\(=\)P? and restricted partitions
• Reduction of the three-partition problem
• On the complexity of some Euclidean problems of partitioning a finite set of points

Cited in

(24)

• A comment on \('NP=P?'\) and restricted partitions
• The parallel complexity of coarsest set partition problems
• Reduction of the three-partition problem
• On the complexity of assembly partitioning
• Momentopes, the complexity of vector partitioning, and Davenport-Schinzel sequences
• Well-solvable instances for the partition problem
• On the complexity of the partner units decision problem
• Synthesis of discrete circuits in a PLD basis
• Tractability frontiers of the partner units configuration problem
• Computational complexity of the product partition problem
• scientific article; zbMATH DE number 6341750 (Why is no real title available?)
• scientific article; zbMATH DE number 5005081 (Why is no real title available?)
• On clustering without replication in combinatorial circuits
• scientific article; zbMATH DE number 3934404 (Why is no real title available?)
• The unbiased black-box complexity of partition is polynomial
• Open Problems in Partition Regularity
• Problems and results on judicious partitions
• Algorithms for constructing the shortest allowable partitions of finite sets
• Relaxed complete partitions: an error-correcting Bachet's problem
• A generic approach to proving NP-hardness of partition type problems
• Two-Dimensional partitioning problems
• ``NP\(=\)P? and restricted partitions
• On the nearest product of partitions
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation

This page was built for publication: On the complexity of some partition problems

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