Some Discrete Optimization Problems With Hamming and H-Comparability Graphs
Keywords:Hamming and H-Comparability Graphs
Any H-comparability graph contains a Hamming graph as spanningsubgraph. An acyclic orientation of an H-comparability graph contains an acyclic orientation of the spanning Hamming graph, called sequence graph in the classical open-shop scheduling problem. We formulate different discrete optimization problems on the Hamming graphs and on H-comparability graphs and consider their complexity and relationship. Moreover, we explore the structures of these graphs in the class of irreducible sequences for the open shop problem in this paper.
How to Cite
© Center for Research, Tribhuvan University