Database Reference
In-Depth Information
Another issue of general interest is concerned with cyclic strings. Sev-
eral methods have been proposed to e
ciently compute the Levenshtein
distance of cyclic strings [10,11,29]. It remains an open problem to deter-
mine medians of this kind of strings.
Acknowledgments
The authors would like to thank K. Abegglen for her contribution to parts
of the chapter.
References
1. Apostolico and Galil, Z. (1997). (eds.),
Pattern Matching Algorithms
, Oxford
University Press.
2. Bunke, H. (1992). Recent Advances in String Matching, in H. Bunke (ed.).
Advances in Structural and Syntactic Pattern Recognition
, World Scientific,
pp. 3-21.
3. Bunke, H., Jiang, X., Abegglen, K., and Kandel, A. (2002). On the Weighted
Mean of a Pair of Strings.
Pattern Analysis and Applications
,
5
(1), 23-30.
4. Casacuberta, F. and de Antoni, M.D. (1997). A Greedy Algorithm for Com-
puting Approximate Median Strings.
Proc. of National Symposium on Pat-
tern Recognition and Image Analysis
, pp. 193-198, Barcelona, Spain.
5. Crochemore, M. and Rytter, W. (1994).
Text Algorithms
, Oxford University
Press.
6. Fagin, R. and Stockmeyer, L. (1998). Relaxing the Triangle Inequality in
Pattern Matching.
Int. Journal on Computer Vision
,
(3), 219-231.
7. Frances, M. and Litman, A. (1997). On Covering Problems of Codes.
Theory
of Computing Systems
,
28
(2), 113-119.
8. Fred, A.L.N. and Leitao, J.M.N. (1998). A Comparative Study of String Dis-
similarity Measures in Structural Clustering.
Proc. of Int. Conf. on Document
Analysis and Recognition
, pp. 385-394.
9. Gramkow, C. (2001). On Averaging Rotations.
Int. Journal on Computer
Vision
,
42
(1/2), 7-16.
10. Gregor, J. and Thomason, M.G. (1993). Dynamic Programming Alignment
of Sequences Representing Cyclic Patterns.
IEEE Trans. on Pattern Analysis
and Machine Intelligence
,
15
(2), 129-135.
11. Gregor, J. and Thomason, M.G. (1996). Ecient Dynamic Programming
Alignment of Cyclic Strings by Shift Elimination.
Pattern Recognition
,
29
(7),
1179-1185.
12. Guimond, A., Meunier, J., and Thirion, J.-P. (2000). Average Brain Models:
A Convergence Study.
Computer Vision and Image Understanding
,
77
(2),
192-210.
13. Gusfield, D. (1997).
Algorithms on Strings, Trees, and Sequences: Computer
Science and Computational Biology
, Cambridge University Press.
30
