Output details
11 - Computer Science and Informatics
University of Strathclyde
Output title
Alternation graphs
Type
E - Conference contribution
Name of conference/published proceedings
Graph-theoretic concepts in computer science : 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers
Volume number
6986
Issue number
-
First page of article
191
ISSN of proceedings
0302-9743
Year of publication
2011
URL
-
Number of additional authors
2
Additional information
<12>This paper is a groundbreaking contribution to the theory of graphs representable by words, which can, among other things, be used to model various scheduling problems. The paper answers a number of previously open questions, and provides a fundamental characterisation theorem for word-representability in terms of certain graph orientations. It will have a major impact by translating the study of word-representable graphs from words to graph orientations, which are often much more tractable. The paper was accepted in 2011 for presentation at WG, a leading international conference in the field.
Interdisciplinary
-
Cross-referral requested
10 - Mathematical Sciences
Research group
A - Theoretical Computer Science
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-