### 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 language | English |
---|---|

Title of host publication | Optimization and Control Methods in Industrial Engineering and Construction |

Publisher | Springer |

Pages | 35-52 |

Number of pages | 18 |

ISBN (Print) | 9789401780445 |

DOIs | |

Publication status | Published - 2014 |

### Publication series

Name | Intelligent Systems, Control and Automation: Science and Engineering |
---|---|

Volume | 72 |

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

*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