Arrays of distinct representatives --- a very simple NP-complete problem
From MaRDI portal
Publication:1363713
DOI10.1016/S0012-365X(97)89167-4zbMATH Open0879.68040MaRDI QIDQ1363713FDOQ1363713
Authors: Dmitry G. Fon-Der-Flaass 
Publication date: 10 August 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
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
Cited In (8)
- Decomposition method for solving a three-index planar assignment problem
- Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
- Sesqui-arrays, a generalisation of triple arrays
- Complexity of list coloring problems with a fixed total number of colors
- Tool switching problems with tool order constraints
- The bilinear assignment problem: complexity and polynomially solvable special cases
- Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
- Tool switching problems in the context of overlay printing with multiple colours
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)
