In this thesis I present some results, which mainly concern finding algorithms for graphs problems, to which I worked on during my Ph.D with the supervision of my supervisors. In particular, as a first theme, it is presented a new temporal interpretation of the well studied \ClusterEditing which we called \EditTempClique (\ETC). In this regard, %at first it is shown that the corresponding versions in the temporal setting of any \NP-Hard version of \ClusterEditing is still \NP-Hard. Then, in this work, it is proved that \ETC is \NP-Complete even if we restrict the possible inputs to the class of temporal graphs with a path as their underlying graph. Furthermore, it is presented a result that shows that \ETC is instead tractable in polynomial time if the underlying graph is a path and the maximum number of appearances allowed for each of the edges of that path is fixed. Taking in mind the known key observation that a static graph is a cluster graph if and only if it does not contain any induced $P_3$, it is presented a local characterisation for cluster temporal graphs. This characterisation establishes that a temporal graph is a cluster temporal graph if and only if every subset of at most five vertices induces a cluster temporal graph. Using this characterisation, we obtain an \FPT~algorithm for \ETC parameterised simultaneously by the number of modifications and the lifetime (number of timesteps) of the input temporal graph. Furthermore, it is shown via a counterexample, that a cluster temporal graph can not be properly characterised by sets of at most four vertices. In the last Chapter of this thesis, at first it is proven a result on the realisation of distance matrices by $n-$cycles and then it is developed an algorithm that allows to establish if a given distance matrix $D$ can or cannot be realised by a weighted unicyclic graph or at least by a weighted tree. In case of affirmative answer, a second part of the algorithm reconstructs that graph. The algorithm takes $\mathcal O(n^4)$. Furthermore, it is shown that if the algorithm returns a unicyclic graph as a realisation of $D$, then this realisation is optimal.

Capresi, C. (2022). Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs..

Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs.

Capresi, Chiara
2022

Abstract

In this thesis I present some results, which mainly concern finding algorithms for graphs problems, to which I worked on during my Ph.D with the supervision of my supervisors. In particular, as a first theme, it is presented a new temporal interpretation of the well studied \ClusterEditing which we called \EditTempClique (\ETC). In this regard, %at first it is shown that the corresponding versions in the temporal setting of any \NP-Hard version of \ClusterEditing is still \NP-Hard. Then, in this work, it is proved that \ETC is \NP-Complete even if we restrict the possible inputs to the class of temporal graphs with a path as their underlying graph. Furthermore, it is presented a result that shows that \ETC is instead tractable in polynomial time if the underlying graph is a path and the maximum number of appearances allowed for each of the edges of that path is fixed. Taking in mind the known key observation that a static graph is a cluster graph if and only if it does not contain any induced $P_3$, it is presented a local characterisation for cluster temporal graphs. This characterisation establishes that a temporal graph is a cluster temporal graph if and only if every subset of at most five vertices induces a cluster temporal graph. Using this characterisation, we obtain an \FPT~algorithm for \ETC parameterised simultaneously by the number of modifications and the lifetime (number of timesteps) of the input temporal graph. Furthermore, it is shown via a counterexample, that a cluster temporal graph can not be properly characterised by sets of at most four vertices. In the last Chapter of this thesis, at first it is proven a result on the realisation of distance matrices by $n-$cycles and then it is developed an algorithm that allows to establish if a given distance matrix $D$ can or cannot be realised by a weighted unicyclic graph or at least by a weighted tree. In case of affirmative answer, a second part of the algorithm reconstructs that graph. The algorithm takes $\mathcal O(n^4)$. Furthermore, it is shown that if the algorithm returns a unicyclic graph as a realisation of $D$, then this realisation is optimal.
Capresi, C. (2022). Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs..
Capresi, Chiara
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/1211314