Open AccessSome Discrete Optimization Problems With Hamming and H-Comparability Graphs
Author(s) -
Tanka Nath Dhamala
Publication year - 2010
Language(s) - English
Resource type - Journals
ISSN - 2091-0916
DOI - 10.3126/tuj.v27i1-2.26400
Subject(s) - comparability , hamming graph , comparability graph , combinatorics , mathematics , cograph , discrete mathematics , hamming distance , line graph , hamming code , graph , pathwidth , algorithm , decoding methods , block code
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.