Journal article
Constructing an indeterminate string from its associated graph
Theoretical Computer Science, Vol.710, pp.88-96
2017
Abstract
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.
Details
- Title
- Constructing an indeterminate string from its associated graph
- Authors/Creators
- J. Helling (Author/Creator)P.J. Ryan (Author/Creator)W.F. Smyth (Author/Creator)M. Soltys (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.710, pp.88-96
- Publisher
- Elsevier BV
- Identifiers
- 991005540272307891
- Copyright
- © 2017 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
205 File views/ downloads
115 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science