Necklaces, convolutions, and \(X+Y\)
type: Item
instance of: scholarly article
title: Necklaces, convolutions, and \(X+Y\)
zbMATH Open document ID: 1360.68498
author: David Bremner
author: Timothy M. Chan
author: Erik D. Demaine
author: Jeff Erickson
author: Ferran Hurtado
author: John Iacono
author: Stefan Langerman
author: Mihai Patrascu
author: Perouz Taslakian
published in: Algorithmica
publication date: 2017-03-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/1212.4771
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 00A65
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6697319
zbMATH Keywords: necklace alignment
zbMATH Keywords: cyclic swap distance
zbMATH Keywords: convolution
zbMATH Keywords: sorting \(X+Y\)
zbMATH Keywords: all pairs shortest paths
MaRDI profile type: Publication
OpenAlex ID: W2174643652
arXiv ID: 1212.4771
cites work: NECKLACE SWAP PROBLEM FOR RHYTHMIC SIMILARITY MEASURES
cites work: Subquadratic algorithms for 3SUM
cites work: Mathematical Programming and the Maximum Transform
cites work: Q5302590
cites work: Time bounds for selection
cites work: Fast algorithms for the maximum convolution problem
cites work: Juggling with pattern matching
cites work: All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
cites work: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
cites work: Self-normalised Distance with Don’t Cares
cites work: Simple deterministic wildcard matching
cites work: Approximate string matching for music analysis
cites work: Combinatorial Pattern Matching
cites work: Verifying candidate matches in sparse and wildcard matching
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: Introduction to algorithms
cites work: Q4267801
cites work: Distance transforms of sampled functions
cites work: Q4055156
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: How good is the information theory bound in sorting?
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: Gauss and the history of the fast Fourier transform
cites work: Q4828997
cites work: Inf-convolution, sous-additivite, convexite des fonctions numériques
cites work: Convex Analysis
cites work: Finding the median
cites work: A pseudo-algorithmic separation of lines from pseudo-lines
cites work: Q4881711
cites work: The Geometry of Musical Rhythm
DOI: 10.1007/S00453-012-9734-3
description: scientific article