The structure of circular decomposable metrics

George Christopher, Martin Farach, Michael Trick

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 1996 - 4th Annual European Symposium, Proceedings
    EditorsJosep Diaz, Maria Serna
    PublisherSpringer Verlag
    Pages486-500
    Number of pages15
    ISBN (Print)3540616802, 9783540616801
    DOIs
    StatePublished - 1996
    Event4th European Symposium on Algorithms, ESA 1996 - Barcelona, Spain
    Duration: Sep 25 1996Sep 27 1996

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1136
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other4th European Symposium on Algorithms, ESA 1996
    Country/TerritorySpain
    CityBarcelona
    Period9/25/969/27/96

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'The structure of circular decomposable metrics'. Together they form a unique fingerprint.

    Cite this