Source author record

Duncan Adamson

Duncan Adamson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

Enumerating m-Length Walks in Directed Graphs with Constant Delay

In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outputting succinct representations of such walks, after a preprocessing step requiring linear time relative to the size of the graph. We apply these results to the problem of enumerating succinct representations of the strings of a given length from a prefix-closed regular language (languages accepted by a finite automaton which has final states only).

preprint2022arXiv

Ranking Binary Unlabelled Necklaces in Polynomial Time

Unlabelled Necklaces are an equivalence class of cyclic words under both the rotation (cyclic shift) and the relabelling operations. The relabelling of a word is a bijective mapping from the alphabet to itself. The main result of the paper is the first polynomial-time algorithm for ranking unlabelled necklaces of a binary alphabet. The time-complexity of the algorithm is $O(n^6 \log^2 n)$, where $n$ is the length of the considered necklaces. The key part of the algorithm is to compute the rank of any word with respect to the set of unlabelled necklaces by finding three other ranks: the rank over all necklaces, the rank over symmetric unlabelled necklaces, and the rank over necklaces with an enclosing labelling. The last two concepts are introduced in this paper.

preprint2020arXiv

The K-Centre Problem for Necklaces

In graph theory, the objective of the k-centre problem is to find a set of $k$ vertices for which the largest distance of any vertex to its closest vertex in the $k$-set is minimised. In this paper, we introduce the $k$-centre problem for sets of necklaces, i.e. the equivalence classes of words under the cyclic shift. This can be seen as the k-centre problem on the complete weighted graph where every necklace is represented by a vertex, and each edge has a weight given by the overlap distance between any pair of necklaces. Similar to the graph case, the goal is to choose $k$ necklaces such that the distance from any word in the language and its nearest centre is minimised. However, in a case of k-centre problem for languages the size of associated graph maybe exponential in relation to the description of the language, i.e., the length of the words l and the size of the alphabet q. We derive several approximation algorithms for the $k$-centre problem on necklaces, with logarithmic approximation factor in the context of l and k, and within a constant factor for a more restricted case.