Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Strathprints

Alternation graphs

Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem (2011) Alternation graphs. In: Graph-theoretic concepts in computer science. Lecture Notes in Computer Science . Springer-Verlag Berlin, Berlin, pp. 191-202. ISBN 9783642258695

Full text not available in this repository. Request a copy from the Strathclyde author

Abstract

A graph G = (V,E) is an alternation graph 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. In this paper we give an effective characterization of alternation graphs in terms of orientations. Namely, we show that a graph is an alternation graph if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about alternation graphs, in particular showing that the recognition problem is in NP, and that alternation graphs include all 3-colorable graphs. We also explore bounds on the size of the word representation of the graph. A graph G is a k-alternation graph if it is represented by a word in which each letter occurs exactly k times; the alternation number of G is the minimum k for which G is a k-alternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.

Item type: Book Section
ID code: 34557
Keywords: alternation graphs, computer science, recognition problem, Electronic computers. Computer science, Computational Theory and Mathematics
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Depositing user: Pure Administrator
Date deposited: 09 Nov 2011 15:08
Last modified: 18 Aug 2017 04:05
URI: https://strathprints.strath.ac.uk/id/eprint/34557
Export data:
CORE (COnnecting REpositories)