scientific article; zbMATH DE number 3934404

MaRDI QIDQ3706500zbMATH OpenFDO

Authors L. G. Tarasova

Publication date 1985

zbMATH Keywords

effective algorithmmaximal composition problems of weighted setsmaximal cut problem in networksNP-completeness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Numerical methods in optimal control (49M99) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 3999286
• On the complexity of some partition problems
• scientific article; zbMATH DE number 3848612
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• NP-completeness of some optimal sequencing problems with a given grouping of elements

Cited in

(4)

• The complexity of combinatorial problems with succinct input representation
• The Computational Complexity of Choice Sets
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• A finite set of functions with an EXPTIME-complete composition problem

This page was built for publication:

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