MS
M.R. Susanna
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>
2 records found
1
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.
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.