Name
Abstract | ||
|---|---|---|
We initiate the study of the minimum distortion problem: Given as input two $n$-point metric spaces, find a bijection between them with minimum distortion. This is an abstraction of certain geometric problems in shape and image matching and is also a natural variation and extension of the fundamental problems of graph isomorphism and bandwidth. Our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. We present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is less than $5+2\sqrt{6}\approx9.9$. We also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080712921 | SIAM Journal on Computing |
Keywords | Field | DocType |
graph isomorphism,optimal bijection,arbitrary unweighted graph,minimum distortion problem,low distortion maps,certain geometric problem,polynomial time algorithm,parameterized polynomial time algorithm,point sets,bounded-degree tree metric,minimum distortion,point metric space,metric spaces,permutations,dynamic programming | Discrete mathematics,Parameterized complexity,Combinatorics,Bijection,Graph isomorphism,Permutation,Distortion problem,Metric space,Time complexity,Distortion,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 4 | 0097-5397 |
ISBN | Citations | PageRank |
1-58113-852-0 | 38 | 1.66 |
References | Authors | |
37 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claire Kenyon | 1 | 38 | 1.66 |
| Yuval Rabani | 2 | 2265 | 274.98 |
| Alistair Sinclair | 3 | 1506 | 308.40 |