Hamiltonian cycles in circulant digraphs with two stripes

Q.F. Yang, R.E. Burkard, E. Çela, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    16 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    The circulant traveling salesman problem (CTSP) is the problem of finding a minimum weight Hamiltonian cycle in a weighted graph with circulant distance matrix. The computational complexity of this problem is not known. In fact, even the complexity of deciding Hamiltonicity of the underlying graph is unknown. This paper provides a characterization of Hamiltonian digraphs with circulant distance matrix containing only two nonzero stripes. The corresponding conditions can be checked in polynomial time. Secondly, we show that all Hamiltonian cycles of a circulant 2-digraph are periodic. Based on these two results, a method for enumerating all Hamiltonian cycles in such digraphs is described. Moreover, two simple algorithms are derived for solving the sum and bottleneck versions of CTSP for circulant distance matrices with two nonzero stripes.
    Original languageEnglish
    Pages (from-to)233-254
    Number of pages22
    JournalDiscrete Mathematics
    Volume176
    Issue number1-3
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'Hamiltonian cycles in circulant digraphs with two stripes'. Together they form a unique fingerprint.

    Cite this