The k-truncated metric dimension of a graph is the minimum number of sensors (a subset of the vertex set) needed to uniquely identify every vertex in the graph based on its distance to the sensors, where the sensors have a measuring range of k. We give an algorithm with the goal that given any tree and any value for the measuring range of the sensors k, the algorithm finds the k-truncated metric dimension of that tree. The algorithm presented in this thesis is a modification of the algorithm given by Gutkovich and Song Yeoh [6]. The algorithm in this thesis improves on their algorithm in both validity and time complexity. We show that given any tree and any value k, the algorithm returns a k-resolving set for that tree. Moreover, we conjecture the difference in the k-truncated metric dimension of any tree and the size of the k-resolving set found by the algorithm for that tree is never greater than one. The time complexity of the algorithm is proven to be O(k3n), where k is the measuring range of the sensors and n is the number of vertices in the tree. This implies that the time complexity is linear in n for fixed k.

This thesis provides you with basic information on graph theory as well as phylogenetic networks, it studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks, based on the manuscript 'Rooting for phylogenetic networks' . Undirected phylogenetic networks can be oriented to become a directed network. In this manuscript the authors come up with multiple algorithms for orienting phylogenetic networks meeting different characteristics. A network is built up of reticulation vertices (where lineages merge) and tree vertices (where lineages separate). A network can be binary, meaning every node in the body of the network has a degree of three or a network can be non-binary, meaning there are no restrictions to the amount of edges a vertex can have.
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website.