Flexible word design and graph labeling

Ming-Yang Kao*, Manan Sanghi, Robert Schweller

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 languageEnglish (US)
Title of host publicationAlgorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
Pages48-60
Number of pages13
DOIs
StatePublished - Dec 1 2006
Event17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India
Duration: Dec 18 2006Dec 20 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Symposium on Algorithms and Computation, ISAAC 2006
CountryIndia
CityKolkata
Period12/18/0612/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

    Kao, M-Y., Sanghi, M., & Schweller, R. (2006). Flexible word design and graph labeling. In 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