Graphs capturing alternations in words

Magnus Halldorsson, Sergey Kitaev, Artem Pyatkin

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

14 Citations (Scopus)

Abstract

A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings
EditorsYuan Gao, Hanlin Lu, Shinnosuke Seki, Sheng Yu
Pages436-437
Number of pages2
DOIs
Publication statusPublished - 2010
Event14th Conference on Dvelopments in Language Theory - London, Ontario, Canada
Duration: 17 Aug 201020 Aug 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6224
ISSN (Print)0302-9743

Conference

Conference14th Conference on Dvelopments in Language Theory
CountryCanada
CityLondon, Ontario
Period17/08/1020/08/10

Keywords

  • algorithm analysis
  • graphs
  • word patterns

Cite this

Halldorsson, M., Kitaev, S., & Pyatkin, A. (2010). Graphs capturing alternations in words. In Y. Gao, H. Lu, S. Seki, & S. Yu (Eds.), Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings (pp. 436-437). (Lecture Notes in Computer Science; Vol. 6224). https://doi.org/10.1007/978-3-642-14455-4_41