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

*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

}

*Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings.*Lecture Notes in Computer Science, vol. 6224, pp. 436-437, 14th Conference on Dvelopments in Language Theory, London, Ontario, Canada, 17/08/10. https://doi.org/10.1007/978-3-642-14455-4_41

**Graphs capturing alternations in words.** / Halldorsson, Magnus; Kitaev, Sergey; Pyatkin, Artem.

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 -