A Linearly-Growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem

Michael Haythorpe, Jerzy Filar

    Research output: Chapter in Book/Report/Conference proceedingChapter

    1 Citation (Scopus)

    Abstract

    We consider a direct conversion of the, classical, set splitting problem to the directed Hamiltonian cycle problem. A constructive procedure for such a conversion is given, and it is shown that the input size of the converted instance is a linear function of the input size of the original instance. A proof that the two instances are equivalent is given, and a procedure for identifying a solution to the original instance from a solution of the converted instance is also provided. We conclude with two examples of set splitting problem instances, one with solutions and one without, and display the corresponding instances of the directed Hamiltonian cycle problem, along with a solution in the first example.

    Original languageEnglish
    Title of host publicationOptimization and Control Methods in Industrial Engineering and Construction
    PublisherSpringer
    Pages35-52
    Number of pages18
    ISBN (Print)9789401780445
    DOIs
    Publication statusPublished - 2014

    Publication series

    NameIntelligent Systems, Control and Automation: Science and Engineering
    Volume72
    ISSN (Print)2213-8986
    ISSN (Electronic)2213-8994

    Fingerprint Dive into the research topics of 'A Linearly-Growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem'. Together they form a unique fingerprint.

  • Cite this

    Haythorpe, M., & Filar, J. (2014). A Linearly-Growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem. In Optimization and Control Methods in Industrial Engineering and Construction (pp. 35-52). (Intelligent Systems, Control and Automation: Science and Engineering; Vol. 72). Springer. https://doi.org/10.1007/978-94-017-8044-5_3