Abstract
| Language | English |
|---|---|
| Title of host publication | Developments in Language Theory |
| Subtitle of host publication | 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings |
| Editors | Yuan Gao, Hanlin Lu, Shinnosuke Seki, Sheng Yu |
| Pages | 436-437 |
| Number of pages | 2 |
| DOIs | |
| Publication status | Published - 2010 |
| Event | 14th Conference on Dvelopments in Language Theory - London, Ontario, Canada Duration: 17 Aug 2010 → 20 Aug 2010 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 6224 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 14th Conference on Dvelopments in Language Theory |
|---|---|
| Country | Canada |
| City | London, Ontario |
| Period | 17/08/10 → 20/08/10 |
Fingerprint
Keywords
- algorithm analysis
- graphs
- word patterns
Cite this
}
Graphs capturing alternations in words. / Halldorsson, Magnus; Kitaev, Sergey; Pyatkin, Artem.
Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. ed. / Yuan Gao; Hanlin Lu; Shinnosuke Seki; Sheng Yu. 2010. p. 436-437 (Lecture Notes in Computer Science; Vol. 6224).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book
TY - GEN
T1 - Graphs capturing alternations in words
AU - Halldorsson, Magnus
AU - Kitaev, Sergey
AU - Pyatkin, Artem
PY - 2010
Y1 - 2010
N2 - 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].
AB - 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].
KW - algorithm analysis
KW - graphs
KW - word patterns
UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/alt2p-final.pdf
U2 - 10.1007/978-3-642-14455-4_41
DO - 10.1007/978-3-642-14455-4_41
M3 - Conference contribution book
SN - 978-3-642-14454-7
T3 - Lecture Notes in Computer Science
SP - 436
EP - 437
BT - Developments in Language Theory
A2 - Gao, Yuan
A2 - Lu, Hanlin
A2 - Seki, Shinnosuke
A2 - Yu, Sheng
ER -