Necklaces, Convolutions, and X + Y

DOI10.1007/11841036_17zbMath1131.68580MaRDI QIDQ5449525

Timothy M. Chan, Erik D. Demaine, John Iacono, Perouz Taslakian, Jeff Erickson, David Bremner, Stefan Langerman, Ferran Hurtado

Publication date: 11 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11841036_17

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68W05: Nonnumerical algorithms

Related Items

Techniques and Open Questions in Computational Convex Analysis, Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems, Combining initial segments of lists, Indexing permutations for binary strings, Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis, On approximate jumbled pattern matching in strings, Computational geometric aspects of rhythm, melody, and voice-leading, Near-linear time approximation schemes for geometric maximum coverage, Characterization of interval graphs that are unpaired 2-disjoint path coverable, A linear-time algorithm for Hamming distance with shifts, Optimal point movement for covering circular regions, Approximating the maximum consecutive subsums of a sequence, Linear Time Approximation Schemes for Geometric Maximum Coverage, Extreme Witnesses and Their Applications