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 Citations (Scopus)

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

Fingerprint

Graph Labeling
Labeling
Hamming distance
Graph in graph theory
Vertex of a graph
DNA
Hamming Distance
Deterministic Algorithm
Randomisation
Maximum Degree
Complement
Adjacent
Strings
Binary
Design

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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
Kao, Ming-Yang ; Sanghi, Manan ; Schweller, Robert. / Flexible word design and graph labeling. Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. pp. 48-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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",
month = "12",
day = "1",
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",

}

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

Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 48-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Kao M-Y, Sanghi M, Schweller R. Flexible word design and graph labeling. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 48-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11940128_7