Approximation to largest graceful subgraphs With constrained conditions
Bing Yao, Hui Dong Cheng, Haixia Tao, Xiangqian Zhou · 2010 3rd International Conference on Biomedical Engineering and Informatics · 2010
Bang-Jensen and Gutin considered the Bennett's model of chromosome arrangement in a cell of an eukaryotic organism. By means of the graph-theoretic model obtained by graph labellings, mathematicians found the solution of this biological system. By reducing an instance of a problem to a standard graph problem, we may be able to use well-known graph algorithms to provide an optimal solution, such as graphs in bioinformatics. The graph bandwidth being one of graph labellings provides a link between the syntactic structure of a constraint satisfaction problem and the complexity of the underlying search task. Graph labellings have inspired research in coding theory problems, in X-ray crystallographic analysis, to design communication network addressing systems, in determining optimal circuit layouts and radio astronomy. The graceful labelling, a typical one of graph labellings, is considered for some interesting problems.