Arrays of distinct representatives --- a very simple NP-complete problem

DOI10.1016/S0012-365X(97)89167-4zbMath0879.68040MaRDI QIDQ1363713

Dmitry G. Fon-Der-Flaass

Publication date: 10 August 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-complete problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Tool switching problems in the context of overlay printing with multiple colours ⋮ Tool switching problems with tool order constraints ⋮ Decomposition method for solving a three-index planar assignment problem ⋮ Sesqui-arrays, a generalisation of triple arrays ⋮ Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms

Cites Work

• Complexity of a 3-dimensional assignment problem
• The list chromatic index of a bipartite multigraph
• Unnamed Item
• Unnamed Item

This page was built for publication: Arrays of distinct representatives --- a very simple NP-complete problem