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

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

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

}

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

**Flexible word design and graph labeling.** / Kao, Ming-Yang; Sanghi, Manan; Schweller, Robert.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Flexible word design and graph labeling

AU - Kao, Ming-Yang

AU - Sanghi, Manan

AU - Schweller, Robert

PY - 2006/12/1

Y1 - 2006/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=77249131309&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77249131309&partnerID=8YFLogxK

U2 - 10.1007/11940128_7

DO - 10.1007/11940128_7

M3 - Conference contribution

AN - SCOPUS:77249131309

SN - 3540496947

SN - 9783540496946

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

SP - 48

EP - 60

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

ER -