Y. Murakami
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
15 records found
1
Problem definition and Research question
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here. ...
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here. ...
Problem definition and Research question
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here.
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here.
Graph Burning
Bounds on the burning number of higher-dimensional grid and king’s graphs
Graph burning models the transmission of viruses and information. Graph burning is an iterative process in which vertices go from unburned to burned. In every round, first, all neighbors of burned vertices are also burned, second, one unburned vertex is selected as a source and also burned. These rounds are repeated until every vertex is burned. The burning number of a graph is the minimum number of rounds needed to burn every vertex in that graph.
Finding the burning number for a general graph is an NP-complete problem. Therefore, computing the burning number for relatively big graphs takes a long time. One way to reduce this time is by finding lower and upper bounds for the burning number that are close to the actual burning number.
In this thesis, we find lower and upper bounds for the burning number of Cartesian and strong products of multiple path graphs. These graphs are also known as higher-dimensional grid and king's graphs. The technique used to find these bounds is based on the technique Mitsche et al. used to asymptotically determine the burning number of grid graphs and king's graphs. A grid graph is the Cartesian product of two path graphs and a king's graph is the strong product of two path graphs.
For the burning number of higher-dimensional grid graphs, we found an implicit lower bound. The lower bound for the burning number of an i-dimensional grid graph can be calculated using the lower bound for the burning number of the (i-1)-dimensional grid graph.
We found that the burning number of the strong product of i paths of length n is larger than 0.5ni/(i+1) and smaller than ⌈0.5(n+1)⌉. For the strong product of i paths of lengths m1,m2,…,mi, we proved the burning number is larger than 0.5∏ij=1mj1/(i+1). ...
Finding the burning number for a general graph is an NP-complete problem. Therefore, computing the burning number for relatively big graphs takes a long time. One way to reduce this time is by finding lower and upper bounds for the burning number that are close to the actual burning number.
In this thesis, we find lower and upper bounds for the burning number of Cartesian and strong products of multiple path graphs. These graphs are also known as higher-dimensional grid and king's graphs. The technique used to find these bounds is based on the technique Mitsche et al. used to asymptotically determine the burning number of grid graphs and king's graphs. A grid graph is the Cartesian product of two path graphs and a king's graph is the strong product of two path graphs.
For the burning number of higher-dimensional grid graphs, we found an implicit lower bound. The lower bound for the burning number of an i-dimensional grid graph can be calculated using the lower bound for the burning number of the (i-1)-dimensional grid graph.
We found that the burning number of the strong product of i paths of length n is larger than 0.5ni/(i+1) and smaller than ⌈0.5(n+1)⌉. For the strong product of i paths of lengths m1,m2,…,mi, we proved the burning number is larger than 0.5∏ij=1mj1/(i+1). ...
Graph burning models the transmission of viruses and information. Graph burning is an iterative process in which vertices go from unburned to burned. In every round, first, all neighbors of burned vertices are also burned, second, one unburned vertex is selected as a source and also burned. These rounds are repeated until every vertex is burned. The burning number of a graph is the minimum number of rounds needed to burn every vertex in that graph.
Finding the burning number for a general graph is an NP-complete problem. Therefore, computing the burning number for relatively big graphs takes a long time. One way to reduce this time is by finding lower and upper bounds for the burning number that are close to the actual burning number.
In this thesis, we find lower and upper bounds for the burning number of Cartesian and strong products of multiple path graphs. These graphs are also known as higher-dimensional grid and king's graphs. The technique used to find these bounds is based on the technique Mitsche et al. used to asymptotically determine the burning number of grid graphs and king's graphs. A grid graph is the Cartesian product of two path graphs and a king's graph is the strong product of two path graphs.
For the burning number of higher-dimensional grid graphs, we found an implicit lower bound. The lower bound for the burning number of an i-dimensional grid graph can be calculated using the lower bound for the burning number of the (i-1)-dimensional grid graph.
We found that the burning number of the strong product of i paths of length n is larger than 0.5ni/(i+1) and smaller than ⌈0.5(n+1)⌉. For the strong product of i paths of lengths m1,m2,…,mi, we proved the burning number is larger than 0.5∏ij=1mj1/(i+1).
Finding the burning number for a general graph is an NP-complete problem. Therefore, computing the burning number for relatively big graphs takes a long time. One way to reduce this time is by finding lower and upper bounds for the burning number that are close to the actual burning number.
In this thesis, we find lower and upper bounds for the burning number of Cartesian and strong products of multiple path graphs. These graphs are also known as higher-dimensional grid and king's graphs. The technique used to find these bounds is based on the technique Mitsche et al. used to asymptotically determine the burning number of grid graphs and king's graphs. A grid graph is the Cartesian product of two path graphs and a king's graph is the strong product of two path graphs.
For the burning number of higher-dimensional grid graphs, we found an implicit lower bound. The lower bound for the burning number of an i-dimensional grid graph can be calculated using the lower bound for the burning number of the (i-1)-dimensional grid graph.
We found that the burning number of the strong product of i paths of length n is larger than 0.5ni/(i+1) and smaller than ⌈0.5(n+1)⌉. For the strong product of i paths of lengths m1,m2,…,mi, we proved the burning number is larger than 0.5∏ij=1mj1/(i+1).
Degree-Constrained Graph Burning
Extremal Bounds, Regular Constructions, and 𝛼-Angular Trees
Graph burning is a discrete-time process on a graph that models the spread of information or influence. At each time step, an unburned vertex may be chosen as a source of fire, after which the fire spreads from previously burned vertices to their neighbors. The minimum number of time steps required to burn all vertices is called the burning number 𝑏(𝐺) of a graph 𝐺.
In many applications, networks are subject to capacity limitations, such as a bounded number of connections per vertex. We study degree-constrained graphs and their extremal behavior.
For connected graphs of bounded maximum degree Δ and a fixed burning number 𝑏, we determine the maximum possible order. We show that this bound is of order 𝒪(Δ𝑏−1). We also show that this bound is tight via explicit constructions, which yields a logarithmic lower bound of the form 𝑏(𝐺) ≥ Ω(log_(Δ−1) 𝑛). We further show a more narrow bound in the 𝑑-regular setting and prove this is also tight via explicit constructions.
We further consider the complementary problem of constructing 𝑑-regular graphs with large burning numbers. We introduce the family of 𝑑-necklaces and show that their burning numbers match the known asymptotic upper bound of Martinsson up to an additive constant of one. These graphs also achieve the corresponding upper bound for the radius of Kim et al. up to an additive constant of one.
Finally, for restricted tree classes, we obtain improved asymptotic upper bounds on the burning number by adapting an existing framework. One consequence is an asymptotic refinement by a factor of 1/√2 of the known bound for homeomorphically irreducible trees of Murakami.
Graph burning is a discrete-time process on a graph that models the spread of information or influence. At each time step, an unburned vertex may be chosen as a source of fire, after which the fire spreads from previously burned vertices to their neighbors. The minimum number of time steps required to burn all vertices is called the burning number 𝑏(𝐺) of a graph 𝐺.
In many applications, networks are subject to capacity limitations, such as a bounded number of connections per vertex. We study degree-constrained graphs and their extremal behavior.
For connected graphs of bounded maximum degree Δ and a fixed burning number 𝑏, we determine the maximum possible order. We show that this bound is of order 𝒪(Δ𝑏−1). We also show that this bound is tight via explicit constructions, which yields a logarithmic lower bound of the form 𝑏(𝐺) ≥ Ω(log_(Δ−1) 𝑛). We further show a more narrow bound in the 𝑑-regular setting and prove this is also tight via explicit constructions.
We further consider the complementary problem of constructing 𝑑-regular graphs with large burning numbers. We introduce the family of 𝑑-necklaces and show that their burning numbers match the known asymptotic upper bound of Martinsson up to an additive constant of one. These graphs also achieve the corresponding upper bound for the radius of Kim et al. up to an additive constant of one.
Finally, for restricted tree classes, we obtain improved asymptotic upper bounds on the burning number by adapting an existing framework. One consequence is an asymptotic refinement by a factor of 1/√2 of the known bound for homeomorphically irreducible trees of Murakami.
Spectra of binary rooted phylogenetic trees
Exploring the link between tree topology and eigenvalue patterns
Phylogenetic trees have been used for decades to visualize evolutionary relationships graphically. Comparing topologies of trees is essential to many research areas of biology, but is complicated due to their combinatorial nature and the number of possible topologies that increases with the number of species. We will focus on binary rooted phylogenetic trees with unit edge length. Comparison can be facilitated by investigating the spectra - the set of eigenvalues - of the pairwise distance matrices of these trees. A pair of distinct trees on 17 leaves with equal spectrum already showed that spectra are not unique for the topology of the tree, however, they reveal some (sub-)structures.
In this thesis, we show that eigenvalue -2 with corresponding eigenvector v =-e_i+e_j reveals the presence of a cherry (two current species sharing a parent). Moreover, we prove that perfectly balanced trees have negative spectrum of the closed-form -2(2^k-1), where k is a number between 1 and the height of the tree. In addition, we show that an eigenvalue lambda of a submatrix appears in the spectrum of the full matrix, as long as the part of the matrix linking the subtree to the rest of the tree is orthogonal to the submatrix’s eigenvector corresponding to lambda. The remaining eigenvalues of the full matrix can be computed using Schur's formula. Finally, we combine all these results and explain the spectral equivalence in the pair of distinct trees on 17 leaves. We observe that other eigenvalues that appear in this spectrum might reveal another type of subtree. ...
In this thesis, we show that eigenvalue -2 with corresponding eigenvector v =-e_i+e_j reveals the presence of a cherry (two current species sharing a parent). Moreover, we prove that perfectly balanced trees have negative spectrum of the closed-form -2(2^k-1), where k is a number between 1 and the height of the tree. In addition, we show that an eigenvalue lambda of a submatrix appears in the spectrum of the full matrix, as long as the part of the matrix linking the subtree to the rest of the tree is orthogonal to the submatrix’s eigenvector corresponding to lambda. The remaining eigenvalues of the full matrix can be computed using Schur's formula. Finally, we combine all these results and explain the spectral equivalence in the pair of distinct trees on 17 leaves. We observe that other eigenvalues that appear in this spectrum might reveal another type of subtree. ...
Phylogenetic trees have been used for decades to visualize evolutionary relationships graphically. Comparing topologies of trees is essential to many research areas of biology, but is complicated due to their combinatorial nature and the number of possible topologies that increases with the number of species. We will focus on binary rooted phylogenetic trees with unit edge length. Comparison can be facilitated by investigating the spectra - the set of eigenvalues - of the pairwise distance matrices of these trees. A pair of distinct trees on 17 leaves with equal spectrum already showed that spectra are not unique for the topology of the tree, however, they reveal some (sub-)structures.
In this thesis, we show that eigenvalue -2 with corresponding eigenvector v =-e_i+e_j reveals the presence of a cherry (two current species sharing a parent). Moreover, we prove that perfectly balanced trees have negative spectrum of the closed-form -2(2^k-1), where k is a number between 1 and the height of the tree. In addition, we show that an eigenvalue lambda of a submatrix appears in the spectrum of the full matrix, as long as the part of the matrix linking the subtree to the rest of the tree is orthogonal to the submatrix’s eigenvector corresponding to lambda. The remaining eigenvalues of the full matrix can be computed using Schur's formula. Finally, we combine all these results and explain the spectral equivalence in the pair of distinct trees on 17 leaves. We observe that other eigenvalues that appear in this spectrum might reveal another type of subtree.
In this thesis, we show that eigenvalue -2 with corresponding eigenvector v =-e_i+e_j reveals the presence of a cherry (two current species sharing a parent). Moreover, we prove that perfectly balanced trees have negative spectrum of the closed-form -2(2^k-1), where k is a number between 1 and the height of the tree. In addition, we show that an eigenvalue lambda of a submatrix appears in the spectrum of the full matrix, as long as the part of the matrix linking the subtree to the rest of the tree is orthogonal to the submatrix’s eigenvector corresponding to lambda. The remaining eigenvalues of the full matrix can be computed using Schur's formula. Finally, we combine all these results and explain the spectral equivalence in the pair of distinct trees on 17 leaves. We observe that other eigenvalues that appear in this spectrum might reveal another type of subtree.
This thesis investigates optimization-based control allocation methods designed for fault-tolerant and scalable application in multi-stage rockets. It is particularly focused on rockets with Thrust Vector Control (TVC), aerodynamic fins and Reaction Control Systems (RCS). The aim is to minimize the error between control commands and actuator output, besides actuator effort. Both in nominal and faulty conditions. Three convex optimization formulations are proposed: an Angle-Deflection (AD) problem, a linearized problem and a Second-Order Cone Programming (SOCP) problem. The AD problem includes actuator deflections and the linearized and SOCP formulations jointly consider actuator deflections and engine throttling. This work allows integration of faulty scenarios by constraint tightening, allowing reconfiguration of control allocation without changing the problem structure. Simulation data is used to validate the effectiveness of the formulations in satisfying control commands and fault handling. The work contributes to fault-tolerant and scalable control allocation frameworks.
...
This thesis investigates optimization-based control allocation methods designed for fault-tolerant and scalable application in multi-stage rockets. It is particularly focused on rockets with Thrust Vector Control (TVC), aerodynamic fins and Reaction Control Systems (RCS). The aim is to minimize the error between control commands and actuator output, besides actuator effort. Both in nominal and faulty conditions. Three convex optimization formulations are proposed: an Angle-Deflection (AD) problem, a linearized problem and a Second-Order Cone Programming (SOCP) problem. The AD problem includes actuator deflections and the linearized and SOCP formulations jointly consider actuator deflections and engine throttling. This work allows integration of faulty scenarios by constraint tightening, allowing reconfiguration of control allocation without changing the problem structure. Simulation data is used to validate the effectiveness of the formulations in satisfying control commands and fault handling. The work contributes to fault-tolerant and scalable control allocation frameworks.
Stemmatology is the study and reconstruction of textual genealogy and has several similarities to phylogenetics, the study of evolutionary histories of species. Current methods in computational stemmatology often borrow tools from phylogenetics, yet classical phylogenetic models are not well suited to the structural and labelling requirements of manuscript traditions. In particular, phylogenetics typically assumes leaf-labelled trees or networks and lacks the means to accommodate internal labels—a feature which is crucial in stemmatology. Nonetheless, these models are frequently used as there are few formal alternatives.
This thesis addresses that gap by studying the encoding and reconstruction of internally labelled trees and networks from rooted triplets. Specifically, we consider three classes of graphs: multifurcating rooted trees, general rooted trees (allowing nodes with out-degree one), and level-1 networks. Each graph is assumed to have labels on a subset of its vertices, including all leaves and some internal nodes. We prove that, under limited assumptions, a complete set of rooted triplets uniquely determines the structure and labelling of each of these graph classes up to isomorphism. This generalises earlier results for leaf-labelled binary trees and extends triplet-based encoding to structures with internal labelling and limited reticulation.
Building on these encoding theorems, we develop polynomial-time algorithms to reconstruct each graph class from its full triplet set. For trees, our methods generalise previously proposed algorithms by allowing multifurcations, nodes with out-degree one, and labels at internal vertices. For level-1 networks, we design a reconstruction algorithm that correctly identifies cycle structures and label placement, adapting earlier techniques for dense triplet sets. All reconstruction algorithms are proven correct and theoretically efficient under the given assumptions. The algorithms have been tested on many instances and run quickly.
To compare internally labelled graphs, we introduce an extension of the classical triplet distance. This adapted metric counts differences in triplet sets between two graphs on the same label set. We evaluate the metric and reconstruction algorithms on synthetic and real-world data, demonstrating their ability to capture meaningful structural differences and to recover known graphs from complete or near-complete triplet information. These results show that rooted triplets form a robust foundation for reasoning about internally labelled structures in both tree-like and mildly reticulate settings. The theory and algorithms presented in this thesis provide new tools for computational phylogenetics and stemmatology, enabling the reconstruction and comparison of complex transmission histories from local relational constraints.
Link to the GitHub page containing all the code - https://github.com/TMALevert/LAOML ...
This thesis addresses that gap by studying the encoding and reconstruction of internally labelled trees and networks from rooted triplets. Specifically, we consider three classes of graphs: multifurcating rooted trees, general rooted trees (allowing nodes with out-degree one), and level-1 networks. Each graph is assumed to have labels on a subset of its vertices, including all leaves and some internal nodes. We prove that, under limited assumptions, a complete set of rooted triplets uniquely determines the structure and labelling of each of these graph classes up to isomorphism. This generalises earlier results for leaf-labelled binary trees and extends triplet-based encoding to structures with internal labelling and limited reticulation.
Building on these encoding theorems, we develop polynomial-time algorithms to reconstruct each graph class from its full triplet set. For trees, our methods generalise previously proposed algorithms by allowing multifurcations, nodes with out-degree one, and labels at internal vertices. For level-1 networks, we design a reconstruction algorithm that correctly identifies cycle structures and label placement, adapting earlier techniques for dense triplet sets. All reconstruction algorithms are proven correct and theoretically efficient under the given assumptions. The algorithms have been tested on many instances and run quickly.
To compare internally labelled graphs, we introduce an extension of the classical triplet distance. This adapted metric counts differences in triplet sets between two graphs on the same label set. We evaluate the metric and reconstruction algorithms on synthetic and real-world data, demonstrating their ability to capture meaningful structural differences and to recover known graphs from complete or near-complete triplet information. These results show that rooted triplets form a robust foundation for reasoning about internally labelled structures in both tree-like and mildly reticulate settings. The theory and algorithms presented in this thesis provide new tools for computational phylogenetics and stemmatology, enabling the reconstruction and comparison of complex transmission histories from local relational constraints.
Link to the GitHub page containing all the code - https://github.com/TMALevert/LAOML ...
Stemmatology is the study and reconstruction of textual genealogy and has several similarities to phylogenetics, the study of evolutionary histories of species. Current methods in computational stemmatology often borrow tools from phylogenetics, yet classical phylogenetic models are not well suited to the structural and labelling requirements of manuscript traditions. In particular, phylogenetics typically assumes leaf-labelled trees or networks and lacks the means to accommodate internal labels—a feature which is crucial in stemmatology. Nonetheless, these models are frequently used as there are few formal alternatives.
This thesis addresses that gap by studying the encoding and reconstruction of internally labelled trees and networks from rooted triplets. Specifically, we consider three classes of graphs: multifurcating rooted trees, general rooted trees (allowing nodes with out-degree one), and level-1 networks. Each graph is assumed to have labels on a subset of its vertices, including all leaves and some internal nodes. We prove that, under limited assumptions, a complete set of rooted triplets uniquely determines the structure and labelling of each of these graph classes up to isomorphism. This generalises earlier results for leaf-labelled binary trees and extends triplet-based encoding to structures with internal labelling and limited reticulation.
Building on these encoding theorems, we develop polynomial-time algorithms to reconstruct each graph class from its full triplet set. For trees, our methods generalise previously proposed algorithms by allowing multifurcations, nodes with out-degree one, and labels at internal vertices. For level-1 networks, we design a reconstruction algorithm that correctly identifies cycle structures and label placement, adapting earlier techniques for dense triplet sets. All reconstruction algorithms are proven correct and theoretically efficient under the given assumptions. The algorithms have been tested on many instances and run quickly.
To compare internally labelled graphs, we introduce an extension of the classical triplet distance. This adapted metric counts differences in triplet sets between two graphs on the same label set. We evaluate the metric and reconstruction algorithms on synthetic and real-world data, demonstrating their ability to capture meaningful structural differences and to recover known graphs from complete or near-complete triplet information. These results show that rooted triplets form a robust foundation for reasoning about internally labelled structures in both tree-like and mildly reticulate settings. The theory and algorithms presented in this thesis provide new tools for computational phylogenetics and stemmatology, enabling the reconstruction and comparison of complex transmission histories from local relational constraints.
Link to the GitHub page containing all the code - https://github.com/TMALevert/LAOML
This thesis addresses that gap by studying the encoding and reconstruction of internally labelled trees and networks from rooted triplets. Specifically, we consider three classes of graphs: multifurcating rooted trees, general rooted trees (allowing nodes with out-degree one), and level-1 networks. Each graph is assumed to have labels on a subset of its vertices, including all leaves and some internal nodes. We prove that, under limited assumptions, a complete set of rooted triplets uniquely determines the structure and labelling of each of these graph classes up to isomorphism. This generalises earlier results for leaf-labelled binary trees and extends triplet-based encoding to structures with internal labelling and limited reticulation.
Building on these encoding theorems, we develop polynomial-time algorithms to reconstruct each graph class from its full triplet set. For trees, our methods generalise previously proposed algorithms by allowing multifurcations, nodes with out-degree one, and labels at internal vertices. For level-1 networks, we design a reconstruction algorithm that correctly identifies cycle structures and label placement, adapting earlier techniques for dense triplet sets. All reconstruction algorithms are proven correct and theoretically efficient under the given assumptions. The algorithms have been tested on many instances and run quickly.
To compare internally labelled graphs, we introduce an extension of the classical triplet distance. This adapted metric counts differences in triplet sets between two graphs on the same label set. We evaluate the metric and reconstruction algorithms on synthetic and real-world data, demonstrating their ability to capture meaningful structural differences and to recover known graphs from complete or near-complete triplet information. These results show that rooted triplets form a robust foundation for reasoning about internally labelled structures in both tree-like and mildly reticulate settings. The theory and algorithms presented in this thesis provide new tools for computational phylogenetics and stemmatology, enabling the reconstruction and comparison of complex transmission histories from local relational constraints.
Link to the GitHub page containing all the code - https://github.com/TMALevert/LAOML
Graph Burning
On necklace graphs and cycle-forests
Graph burning is a process that models the spread of information through a network. This process is divided into rounds and is visualized as a spreading fire. Each round, a source of fire may be chosen from where the fire spreads and burns surrounding points. From every burned point, the fire propagates through adjacent points, eventually covering the entire network. The burning number of a graph, b(G), was introduced to measure the time required to burn the entire network.
It was proven that path graphs on n vertices have burning number ⌈√n⌉. It was then conjectured that all connected graphs have at most this burning number. The burning number has been estimated or identified for several classes of graphs. We provide a lower and upper bound for the burning number of a new class of graphs with a path-like structure, namely necklace graphs. Necklace graphs are constructed by concatenating smaller graphs, called pearls. To obtain bounds, we define lower-bound paths and upper-bound paths, which are paths connecting two designated vertices. We show that a lower-bound path always exists in the form of a shortest path, while finding an upper-bound path for an arbitrary necklace is NP-complete. For necklace graphs where a shortest path is an upper-bound path, we show that the burning number can take only two values.
Finally, we consider cycle-forests, which are disconnected graphs whose components are cycle graphs. We prove that burning cycle-forests is NP-complete. ...
It was proven that path graphs on n vertices have burning number ⌈√n⌉. It was then conjectured that all connected graphs have at most this burning number. The burning number has been estimated or identified for several classes of graphs. We provide a lower and upper bound for the burning number of a new class of graphs with a path-like structure, namely necklace graphs. Necklace graphs are constructed by concatenating smaller graphs, called pearls. To obtain bounds, we define lower-bound paths and upper-bound paths, which are paths connecting two designated vertices. We show that a lower-bound path always exists in the form of a shortest path, while finding an upper-bound path for an arbitrary necklace is NP-complete. For necklace graphs where a shortest path is an upper-bound path, we show that the burning number can take only two values.
Finally, we consider cycle-forests, which are disconnected graphs whose components are cycle graphs. We prove that burning cycle-forests is NP-complete. ...
Graph burning is a process that models the spread of information through a network. This process is divided into rounds and is visualized as a spreading fire. Each round, a source of fire may be chosen from where the fire spreads and burns surrounding points. From every burned point, the fire propagates through adjacent points, eventually covering the entire network. The burning number of a graph, b(G), was introduced to measure the time required to burn the entire network.
It was proven that path graphs on n vertices have burning number ⌈√n⌉. It was then conjectured that all connected graphs have at most this burning number. The burning number has been estimated or identified for several classes of graphs. We provide a lower and upper bound for the burning number of a new class of graphs with a path-like structure, namely necklace graphs. Necklace graphs are constructed by concatenating smaller graphs, called pearls. To obtain bounds, we define lower-bound paths and upper-bound paths, which are paths connecting two designated vertices. We show that a lower-bound path always exists in the form of a shortest path, while finding an upper-bound path for an arbitrary necklace is NP-complete. For necklace graphs where a shortest path is an upper-bound path, we show that the burning number can take only two values.
Finally, we consider cycle-forests, which are disconnected graphs whose components are cycle graphs. We prove that burning cycle-forests is NP-complete.
It was proven that path graphs on n vertices have burning number ⌈√n⌉. It was then conjectured that all connected graphs have at most this burning number. The burning number has been estimated or identified for several classes of graphs. We provide a lower and upper bound for the burning number of a new class of graphs with a path-like structure, namely necklace graphs. Necklace graphs are constructed by concatenating smaller graphs, called pearls. To obtain bounds, we define lower-bound paths and upper-bound paths, which are paths connecting two designated vertices. We show that a lower-bound path always exists in the form of a shortest path, while finding an upper-bound path for an arbitrary necklace is NP-complete. For necklace graphs where a shortest path is an upper-bound path, we show that the burning number can take only two values.
Finally, we consider cycle-forests, which are disconnected graphs whose components are cycle graphs. We prove that burning cycle-forests is NP-complete.
Graph burning and cooling
An interactive, probabilistic and optimization approach
Networks appear in many important areas such as transportation systems, social interactions, and computer infrastructures. Understanding how processes spread across such systems is essential for predicting and controlling events like the transmission of diseases, the diffusion of information, or the spread of computer viruses.
This thesis studies the burning number, a measure that indicates the speed at which a process spreads over a network. While most existing research assumes a standard burning process in which every neighbor of a burning node becomes burned with probability 1, this work extends the model to a different setting. We develop an algorithm that incorporates a probability of spreading less than 1, allowing us to compute the expected number of rounds needed to burn an entire graph for any given sequence of nodes. This approach provides more realistic insights into spreading processes and can be applied to a variety of real-world problems.
In addition to the theoretical contribution, we also design and implement an interactive Python tool that visualizes and simulates the burning process for any user-specified graph. This tool makes it possible to experiment with different graphs and contributes to better understanding, teaching, and exploration of the burning number problem.
Finally, this thesis also addresses the related concept the cooling number. For this problem we introduce an integer linear program (ILP) formulation and propose a 2-approximation algorithm to compute a lower bound of the cooling number quickly.
We stated a conjecture about 3-legged spider graphs. This conjecture claims that there exists an optimal cooling sequence such that the source nodes are clustered per leg. As a first step towards the proof of the conjecture, we showed that for a general spider, all the sources of one leg can be clustered at the start of the cooling sequence. ...
This thesis studies the burning number, a measure that indicates the speed at which a process spreads over a network. While most existing research assumes a standard burning process in which every neighbor of a burning node becomes burned with probability 1, this work extends the model to a different setting. We develop an algorithm that incorporates a probability of spreading less than 1, allowing us to compute the expected number of rounds needed to burn an entire graph for any given sequence of nodes. This approach provides more realistic insights into spreading processes and can be applied to a variety of real-world problems.
In addition to the theoretical contribution, we also design and implement an interactive Python tool that visualizes and simulates the burning process for any user-specified graph. This tool makes it possible to experiment with different graphs and contributes to better understanding, teaching, and exploration of the burning number problem.
Finally, this thesis also addresses the related concept the cooling number. For this problem we introduce an integer linear program (ILP) formulation and propose a 2-approximation algorithm to compute a lower bound of the cooling number quickly.
We stated a conjecture about 3-legged spider graphs. This conjecture claims that there exists an optimal cooling sequence such that the source nodes are clustered per leg. As a first step towards the proof of the conjecture, we showed that for a general spider, all the sources of one leg can be clustered at the start of the cooling sequence. ...
Networks appear in many important areas such as transportation systems, social interactions, and computer infrastructures. Understanding how processes spread across such systems is essential for predicting and controlling events like the transmission of diseases, the diffusion of information, or the spread of computer viruses.
This thesis studies the burning number, a measure that indicates the speed at which a process spreads over a network. While most existing research assumes a standard burning process in which every neighbor of a burning node becomes burned with probability 1, this work extends the model to a different setting. We develop an algorithm that incorporates a probability of spreading less than 1, allowing us to compute the expected number of rounds needed to burn an entire graph for any given sequence of nodes. This approach provides more realistic insights into spreading processes and can be applied to a variety of real-world problems.
In addition to the theoretical contribution, we also design and implement an interactive Python tool that visualizes and simulates the burning process for any user-specified graph. This tool makes it possible to experiment with different graphs and contributes to better understanding, teaching, and exploration of the burning number problem.
Finally, this thesis also addresses the related concept the cooling number. For this problem we introduce an integer linear program (ILP) formulation and propose a 2-approximation algorithm to compute a lower bound of the cooling number quickly.
We stated a conjecture about 3-legged spider graphs. This conjecture claims that there exists an optimal cooling sequence such that the source nodes are clustered per leg. As a first step towards the proof of the conjecture, we showed that for a general spider, all the sources of one leg can be clustered at the start of the cooling sequence.
This thesis studies the burning number, a measure that indicates the speed at which a process spreads over a network. While most existing research assumes a standard burning process in which every neighbor of a burning node becomes burned with probability 1, this work extends the model to a different setting. We develop an algorithm that incorporates a probability of spreading less than 1, allowing us to compute the expected number of rounds needed to burn an entire graph for any given sequence of nodes. This approach provides more realistic insights into spreading processes and can be applied to a variety of real-world problems.
In addition to the theoretical contribution, we also design and implement an interactive Python tool that visualizes and simulates the burning process for any user-specified graph. This tool makes it possible to experiment with different graphs and contributes to better understanding, teaching, and exploration of the burning number problem.
Finally, this thesis also addresses the related concept the cooling number. For this problem we introduce an integer linear program (ILP) formulation and propose a 2-approximation algorithm to compute a lower bound of the cooling number quickly.
We stated a conjecture about 3-legged spider graphs. This conjecture claims that there exists an optimal cooling sequence such that the source nodes are clustered per leg. As a first step towards the proof of the conjecture, we showed that for a general spider, all the sources of one leg can be clustered at the start of the cooling sequence.
The burning number conjecture
On cat-constructs and trees with a single degree-2 vertex
In the last decade the graph burning model was developed to model the spread of information between people. Graph burning is a process that is done in rounds with the aim of spreading information to every connected person in a network. Every round one new source of information may be appointed and information spreads from people who have received it, to all of their connections, just like fire spreads. The burning number of a graph, denoted by 𝑏(𝐺), is the parameter that quantifies the speed of this spread of information. It has been conjectured that the burning number for a connected graph on 𝑛 vertices is at most ⌈√𝑛⌉. We prove the burning number conjecture for cat-constructs. Cat-constructs are trees obtained from a path graph 𝑃𝑛 by adding at most two vertices to subtrees of 𝑃𝑛. We show the burning sequence of a cat-construct may contain one fewer source than its burning number if the number of vertices for the cat-construct is more than the first square bigger than 𝑛. With this result
we show that adding a vertex as a leaf to these cat-constructs and appointing it as a source results in the proof of the burning number conjecture for certain 3-caterpillars. Furthermore we prove the burning number conjecture holds for trees with a single degree-2 vertex.
...
In the last decade the graph burning model was developed to model the spread of information between people. Graph burning is a process that is done in rounds with the aim of spreading information to every connected person in a network. Every round one new source of information may be appointed and information spreads from people who have received it, to all of their connections, just like fire spreads. The burning number of a graph, denoted by 𝑏(𝐺), is the parameter that quantifies the speed of this spread of information. It has been conjectured that the burning number for a connected graph on 𝑛 vertices is at most ⌈√𝑛⌉. We prove the burning number conjecture for cat-constructs. Cat-constructs are trees obtained from a path graph 𝑃𝑛 by adding at most two vertices to subtrees of 𝑃𝑛. We show the burning sequence of a cat-construct may contain one fewer source than its burning number if the number of vertices for the cat-construct is more than the first square bigger than 𝑛. With this result
we show that adding a vertex as a leaf to these cat-constructs and appointing it as a source results in the proof of the burning number conjecture for certain 3-caterpillars. Furthermore we prove the burning number conjecture holds for trees with a single degree-2 vertex.
Phylogenetic trees are used to represent evolutionary history of, among others, species, genes or languages. Phylogenetic trees can be reduced by so called cherry-picking sequences. In this thesis we take a closer look at cherry-picking sequences to obtain a more fundamental understanding on the structure and behaviour of these sequences on phylogenetic trees. For binary rooted trees, that is trees with a root, outdegree-2 tree nodes, and a set of leaves, we count the number of sequences that can reduce such trees. Furthermore, we try to find the number of sequences of a given tree that is needed to reduce all subtrees of a given tree. Thus, an enumeration problem and an optimization problem are considered in this thesis. For both problems, we first look for results on simply structured trees, such as caterpillars and double caterpillars. Lastly, we try to expand these results to general binary trees in order to find the answers to the two problems.
...
Phylogenetic trees are used to represent evolutionary history of, among others, species, genes or languages. Phylogenetic trees can be reduced by so called cherry-picking sequences. In this thesis we take a closer look at cherry-picking sequences to obtain a more fundamental understanding on the structure and behaviour of these sequences on phylogenetic trees. For binary rooted trees, that is trees with a root, outdegree-2 tree nodes, and a set of leaves, we count the number of sequences that can reduce such trees. Furthermore, we try to find the number of sequences of a given tree that is needed to reduce all subtrees of a given tree. Thus, an enumeration problem and an optimization problem are considered in this thesis. For both problems, we first look for results on simply structured trees, such as caterpillars and double caterpillars. Lastly, we try to expand these results to general binary trees in order to find the answers to the two problems.
This thesis is on the subject of phylogenetic networks. These are schematic
visualisations used mainly to investigate the evolutionary history of species,
but which can be used for any set of distinguishable elements which have diverged from a common ancestor through some evolutionary process. The research specifically focuses on a way to encode these phylogenetic networks, called μ-representation, which enables researchers to efficiently compare networks in polynomial time. The main contribution of this thesis lies in demonstrating that there are certain classes of phylogenetic networks for which the μ-representation or a modified version thereof serves as a unique encoding and can therefore be used to generate a metric for comparison. Additionally, it is shown that these results do not extend to some other classes of networks. Furthermore, this research shows that certain other information can be gained from analysing the μ-representation of a network, such as which nodes are adjacent to so-called bridges or cut-edges, and what the in-degrees of the nodes in the network are. ...
visualisations used mainly to investigate the evolutionary history of species,
but which can be used for any set of distinguishable elements which have diverged from a common ancestor through some evolutionary process. The research specifically focuses on a way to encode these phylogenetic networks, called μ-representation, which enables researchers to efficiently compare networks in polynomial time. The main contribution of this thesis lies in demonstrating that there are certain classes of phylogenetic networks for which the μ-representation or a modified version thereof serves as a unique encoding and can therefore be used to generate a metric for comparison. Additionally, it is shown that these results do not extend to some other classes of networks. Furthermore, this research shows that certain other information can be gained from analysing the μ-representation of a network, such as which nodes are adjacent to so-called bridges or cut-edges, and what the in-degrees of the nodes in the network are. ...
This thesis is on the subject of phylogenetic networks. These are schematic
visualisations used mainly to investigate the evolutionary history of species,
but which can be used for any set of distinguishable elements which have diverged from a common ancestor through some evolutionary process. The research specifically focuses on a way to encode these phylogenetic networks, called μ-representation, which enables researchers to efficiently compare networks in polynomial time. The main contribution of this thesis lies in demonstrating that there are certain classes of phylogenetic networks for which the μ-representation or a modified version thereof serves as a unique encoding and can therefore be used to generate a metric for comparison. Additionally, it is shown that these results do not extend to some other classes of networks. Furthermore, this research shows that certain other information can be gained from analysing the μ-representation of a network, such as which nodes are adjacent to so-called bridges or cut-edges, and what the in-degrees of the nodes in the network are.
visualisations used mainly to investigate the evolutionary history of species,
but which can be used for any set of distinguishable elements which have diverged from a common ancestor through some evolutionary process. The research specifically focuses on a way to encode these phylogenetic networks, called μ-representation, which enables researchers to efficiently compare networks in polynomial time. The main contribution of this thesis lies in demonstrating that there are certain classes of phylogenetic networks for which the μ-representation or a modified version thereof serves as a unique encoding and can therefore be used to generate a metric for comparison. Additionally, it is shown that these results do not extend to some other classes of networks. Furthermore, this research shows that certain other information can be gained from analysing the μ-representation of a network, such as which nodes are adjacent to so-called bridges or cut-edges, and what the in-degrees of the nodes in the network are.
In phylogenetics, it is important to figure out what method to obtain a phylogenetic tree, a tree showing how species evolve from one another, is more reliable. A phylogenetic tree is a mathematical tree, where every internal vertex has at least 2 children, and the leaves are labeled bijectively with a set $X$. One useful tool to help determine what method is more reliable is to find the rooted triplet distance between two trees. If the distance from a newly developed tree is far from what we know to be reliable trees, then this method is probably unreliable. For this distance, one should look at how many triplets the trees do not have in common. In this report, we will look at a specific algorithm to compute the rooted triplet distance between two special rooted phylogenetic trees, caterpillars, by checking how many triplets these two caterpillars have in common. In this report, we will map the leaves into $\mathbb{N}^3$ and $\mathbb{N}^d$, to determine how many triplets 3 or $d$ trees have in common. Especially for $\mathbb{N}^d$ it becomes complicated to decide for what regions of $\mathbb{N}^d$ the leaves need to be counted, and for which ones not. After finding the closed-form notation for this, we will also discuss how many terms there are in the sum of this equation. Lastly, we will talk about the time complexity of this algorithm. The idea is that this algorithm will work faster than the naive approach, which runs in $O(n^3)$ time. Due to complications in the third and higher dimensions, this faster running time may or may not be accomplished, depending on whether another algorithm can be found to resolve these complications, which will not be done in this report. A closed-form notation can be found to express the number of triplets two caterpillars do not have in common, and the number of terms this equation has will also be discussed in Chapter 5.
...
In phylogenetics, it is important to figure out what method to obtain a phylogenetic tree, a tree showing how species evolve from one another, is more reliable. A phylogenetic tree is a mathematical tree, where every internal vertex has at least 2 children, and the leaves are labeled bijectively with a set $X$. One useful tool to help determine what method is more reliable is to find the rooted triplet distance between two trees. If the distance from a newly developed tree is far from what we know to be reliable trees, then this method is probably unreliable. For this distance, one should look at how many triplets the trees do not have in common. In this report, we will look at a specific algorithm to compute the rooted triplet distance between two special rooted phylogenetic trees, caterpillars, by checking how many triplets these two caterpillars have in common. In this report, we will map the leaves into $\mathbb{N}^3$ and $\mathbb{N}^d$, to determine how many triplets 3 or $d$ trees have in common. Especially for $\mathbb{N}^d$ it becomes complicated to decide for what regions of $\mathbb{N}^d$ the leaves need to be counted, and for which ones not. After finding the closed-form notation for this, we will also discuss how many terms there are in the sum of this equation. Lastly, we will talk about the time complexity of this algorithm. The idea is that this algorithm will work faster than the naive approach, which runs in $O(n^3)$ time. Due to complications in the third and higher dimensions, this faster running time may or may not be accomplished, depending on whether another algorithm can be found to resolve these complications, which will not be done in this report. A closed-form notation can be found to express the number of triplets two caterpillars do not have in common, and the number of terms this equation has will also be discussed in Chapter 5.
Making phylogenetic networks orchard
Algorithms to determine if a phylogenetic network is orchard and to transform non-orchard to orchard networks
Phylogenetic networks are used to represent evolutionary histories of a set of taxa. In this thesis, we look at a certain network class, called orchard networks.
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks. ...
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks. ...
Phylogenetic networks are used to represent evolutionary histories of a set of taxa. In this thesis, we look at a certain network class, called orchard networks.
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks.
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks.
Reconstruction of Phylogenetic Networks
An algorithm for deconstructing and reconstructing Level-2 Binary Networks based on their distances
Van Iersel, Moulton, and Murakami (2020) proved that a level-2 binary phylogenetic network can be uniquely reconstructed based on the matrix of mulitsets of the distances of the leaves. Using a handful of lemma’s each
describing the steps of identifying cherries, uncontained leaves and blobs in the network, I created an algorithm for deconstruction the theoretical network corresponding to the matrix, and constructing the network based on the deconstruction steps. Unfortunately, this algorithm is not of polynomial time, as in the deconstruction programs are run that take time proportional to the sizes of the multisets of distances, which are upperbounded by 4n, where n is the number of leaves in the network. This algorithm is tested on more than 35000 networks with 10 to 24 leaves, and resulted in no errors. ...
describing the steps of identifying cherries, uncontained leaves and blobs in the network, I created an algorithm for deconstruction the theoretical network corresponding to the matrix, and constructing the network based on the deconstruction steps. Unfortunately, this algorithm is not of polynomial time, as in the deconstruction programs are run that take time proportional to the sizes of the multisets of distances, which are upperbounded by 4n, where n is the number of leaves in the network. This algorithm is tested on more than 35000 networks with 10 to 24 leaves, and resulted in no errors. ...
Van Iersel, Moulton, and Murakami (2020) proved that a level-2 binary phylogenetic network can be uniquely reconstructed based on the matrix of mulitsets of the distances of the leaves. Using a handful of lemma’s each
describing the steps of identifying cherries, uncontained leaves and blobs in the network, I created an algorithm for deconstruction the theoretical network corresponding to the matrix, and constructing the network based on the deconstruction steps. Unfortunately, this algorithm is not of polynomial time, as in the deconstruction programs are run that take time proportional to the sizes of the multisets of distances, which are upperbounded by 4n, where n is the number of leaves in the network. This algorithm is tested on more than 35000 networks with 10 to 24 leaves, and resulted in no errors.
describing the steps of identifying cherries, uncontained leaves and blobs in the network, I created an algorithm for deconstruction the theoretical network corresponding to the matrix, and constructing the network based on the deconstruction steps. Unfortunately, this algorithm is not of polynomial time, as in the deconstruction programs are run that take time proportional to the sizes of the multisets of distances, which are upperbounded by 4n, where n is the number of leaves in the network. This algorithm is tested on more than 35000 networks with 10 to 24 leaves, and resulted in no errors.
Bachelor thesis
(2019)
-
Robbert Huijsman, Leo van Iersel, Yuki Murakami, Remie Janssen, Bart van den Dries
Interest in phylogenetic trees for histories of species and DNA has spawned many problems, one of which is TreeContainment; a problem that asks whether a tree is contained within a network. The TreeContainment problem is proven to be NP-hard for general trees and networks, however it is solvable in polynomial time for networks that meet the tree-child restriction. An algorithm to solve TreeContainment for binary tree-child networks has been created previously with quadratic running time (van Iersel, Semple, Steel, 2010). Janssen and Murakami have recently created a new algorithm that solves a larger problem NetworkContainment, for semi-binary tree-child networks (Janssen, Murakami, 2019). This new algorithm uses tree-child sequences introduced by Linz and Semple, but there has not been an implementation of it until now. In this paper I show an implementation (using Python) of this algorithm, in which I have made a modification that increases its speed on networks with large indegrees. Furthermore I have proven in this paper that the output of this algorithm remains correct under this modification, and that the running time of the modified algorithm is now linear without requiring a constant maximum indegree at all.
...
Interest in phylogenetic trees for histories of species and DNA has spawned many problems, one of which is TreeContainment; a problem that asks whether a tree is contained within a network. The TreeContainment problem is proven to be NP-hard for general trees and networks, however it is solvable in polynomial time for networks that meet the tree-child restriction. An algorithm to solve TreeContainment for binary tree-child networks has been created previously with quadratic running time (van Iersel, Semple, Steel, 2010). Janssen and Murakami have recently created a new algorithm that solves a larger problem NetworkContainment, for semi-binary tree-child networks (Janssen, Murakami, 2019). This new algorithm uses tree-child sequences introduced by Linz and Semple, but there has not been an implementation of it until now. In this paper I show an implementation (using Python) of this algorithm, in which I have made a modification that increases its speed on networks with large indegrees. Furthermore I have proven in this paper that the output of this algorithm remains correct under this modification, and that the running time of the modified algorithm is now linear without requiring a constant maximum indegree at all.