TY - CHAP

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

AU - Haythorpe, Michael

AU - Filar, Jerzy

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84896530000&partnerID=8YFLogxK

U2 - 10.1007/978-94-017-8044-5_3

DO - 10.1007/978-94-017-8044-5_3

M3 - Chapter

SN - 9789401780438

T3 - Intelligent Systems, Control and Automation: Science and Engineering

SP - 35

EP - 52

BT - Optimization and Control Methods in Industrial Engineering and Construction

PB - Springer

ER -