The complexity of binary matrix completion under diameter constraints
From MaRDI portal
Publication:2678254
DOI10.1016/j.jcss.2022.10.001OpenAlexW4307296390MaRDI QIDQ2678254
Vincent Froese, Tomohiro Koana, Rolf Niedermeier
Publication date: 9 January 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.05068
Hamming distancecombinatorial algorithmsNP-hard problemscomplexity dichotomystringologyconsensus problems2-SATsunflowersgraph factors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity analysis for the closest string with wildcards problem
- On covering problems of codes
- Une propriété extremale des plans projectifs finis dans une classe de codes équidistants
- Approximation algorithms for Hamming clustering problems
- Exploiting hidden structure in selecting dimensions that distinguish vectors
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- On the kernelization complexity of string problems
- Polynomial and APX-hard cases of the individual haplotyping problem
- Consensus strings with small maximum distance and small distance sum
- Parametrized complexity theory.
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Extremal Combinatorics
- Clustering lines in high-dimensional space
- Intersection Theorems for Systems of Sets
- Consensus Patterns (Probably) Has no EPTAS
- Finding Consensus Strings with Small Length Difference between Input and Solution Strings
- Tight Hardness Results for Consensus Problems on Circular Strings and Time Series
- Lower Bounds for Approximation Schemes for Closest String
- Clustering Affine Subspaces: Hardness and Algorithms
- Parameterized Algorithms for Matrix Completion with Radius Constraints.
- Analysis of incomplete data and an intrinsic-dimension Helly theorem
- Hard tiling problems with simple tiles
