@inproceedings{fb35a301217047e1b1fd644c18e24c15,

title = "Flexible word design and graph labeling",

abstract = "Motivated by emerging applications for DNA code word design, we consider a generalization of the code word design problem in which an input graph is given which must be labeled with equal length binary strings of minimal length such that the Hamming distance is small between words of adjacent nodes and large between words of non-adjacent nodes. For general graphs we provide algorithms that bound the word length with respect to either the maximum degree of any vertex or the number of edges in either the input graph or its complement. We further provide multiple types of recursive, deterministic algorithms for trees and forests, and provide an improvement for forests that makes use of randomization.",

author = "Ming-Yang Kao and Manan Sanghi and Robert Schweller",

year = "2006",

doi = "10.1007/11940128_7",

language = "English (US)",

isbn = "3540496947",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "48--60",

booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

note = "17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

}