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

DOI10.1016/S0012-365X(97)89167-4MaRDI QIDQ1363713zbMATHFDO

Authors 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)

Recommendations

• Sample complexity of the distinct elements problem
• scientific article; zbMATH DE number 5206701
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• On a Simple Class of Combinatorial Problems
• A Generalization of Distinct Representatives and Its Applications
• NP-completeness of some optimal sequencing problems with a given grouping of elements
• Efficient exact algorithm for count distinct problem
• A simple random assignment problem with a unique solution
• A simplified NP-complete satisfiability problem

Cites work

• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of a 3-dimensional assignment problem
• The list chromatic index of a bipartite multigraph

Cited in

(8)

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

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

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