In this repository you can find small-scaled literature reviews produced by the author as part of optional University assignments they opted for undertaking, during their studies at the Computer Science Department of AUTh. The repository contains two literature reviews, each one accompanied by a presentation file, specifically created by the author for in-class presentation. The topics of the literature reviews are the following:
- A summary of a paper (presented in VLDB 2024) about graph sparsification algorithms
- Insights to work published within 2018-2023 related to spanning tree problems
We summarize the key concepts and results presented in the research paper Demystifying Graph Sparsification Algorithms in Graph Properties Preservation authored by Y. Chen et al. The summary is accompanied by a presentation file designed for in-class presentation.
In this small-scaled literature survey, we provide insights into SoA work and results published within 2018 – 2023 related to spanning tree problems. At first, we investigate problems where, given a set V of n vertices, the goal is to find a tree that connects all n vertices in a way that the maximum weight of an edge in the graph (bottleneck) is minimized. This is called the Minimum Bottleneck Spanning Tree (MBST) problem. We study two interesting variations of the MBST problem; the first imposes a degree upper bound for the vertices of the constructed tree and the latter lets the vertices be linearly moving points in Rdim . However, there exist problems, where minimizing the weight of the whole tree is required, rather than only its maximum-cost edge. This is called the Minimum Spanning Tree (MST) problem. Within the context of this assignment, we elaborate on MST problems where the vertices are moving points, the edges represent the distances between them under some distance function and the objective is to construct a single MST for the whole motion.