Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Constructing an indeterminate string from its associated graph

Helling, J., Ryan, P.J., Smyth, W.F. and Soltys, M. (2017) Constructing an indeterminate string from its associated graph. Theoretical Computer Science, 710 . pp. 88-96.

PDF - Authors' Version
Download (897kB) | Preview
Link to Published Version:
*Subscription may be required


As discussed at length in Christodoulakis et al. (2015) , there is a natural one-many correspondence between simple undirected graphs G with vertex set V=(1,2,...,n) and indeterminate strings x=x[1..n] - that is, sequences of subsets of some alphabet Σ. In this paper, given G, we consider the "reverse engineering" problem of computing a corresponding x on an alphabet Σmin of minimum cardinality. This turns out to be equivalent to the NP-hard problem of computing the intersection number of G, thus in turn equivalent to the clique cover problem. We describe a heuristic algorithm that computes an approximation to Σmin and a corresponding x We give various properties of our algorithm, including some experimental evidence that on average it requires O(n2log n) time. We compare it with other heuristics, and state some conjectures and open problems.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2017 Elsevier B.V.
Item Control Page Item Control Page


Downloads per month over past year