@inproceedings{85418fa8f5b444a790b5b3bc898aa616,
title = "The structure of circular decomposable metrics",
abstract = "Circular decomposable metrics (CDM) are sums of cut metrics that satisfy a circularity condition. A number of combinatorial optimization problems, including the traveling salesman problem, are easily solved if the underlying cost matrix represents a CDM. We give a linear time algorithm for recognizing CDMs and show that they are identical to another class of metrics: the Kalmanson metric.",
author = "George Christopher and Martin Farach and Michael Trick",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 4th European Symposium on Algorithms, ESA 1996 ; Conference date: 25-09-1996 Through 27-09-1996",
year = "1996",
doi = "10.1007/3-540-61680-2_77",
language = "English (US)",
isbn = "3540616802",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "486--500",
editor = "Josep Diaz and Maria Serna",
booktitle = "Algorithms - ESA 1996 - 4th Annual European Symposium, Proceedings",
}