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

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings |

Pages | 48-60 |

Number of pages | 13 |

DOIs | |

State | Published - Dec 1 2006 |

Event | 17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India Duration: Dec 18 2006 → Dec 20 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4288 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 17th International Symposium on Algorithms and Computation, ISAAC 2006 |
---|---|

Country | India |

City | Kolkata |

Period | 12/18/06 → 12/20/06 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Flexible word design and graph labeling'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings*(pp. 48-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS). https://doi.org/10.1007/11940128_7