4 papers
Connected (Dense) Partition for Tree-Like Graphs
Katrin Casel, Archontia C. Giannopoulou, Aikaterini Niklanovits
We focus on two variants of graph partitioning problems, connected partition and dense partition. Formally, given a graph and a partition of its vertices $\mathcal P=\{P_…
Connected Partitions via Connected Dominating Sets
Aikaterini Niklanovits, Kirill Simonov, Shaily Verma +1
The classical theorem due to GyÅri and Lovász states that any -connected graph admits a partition into connected subgraphs, where each subgraph has a prescribed size a…
Combining Crown Structures for Vulnerability Measures
Katrin Casel, Tobias Friedrich, Aikaterini Niklanovits +2
Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted)…
A New Approach for Approximating Directed Rooted Networks
Sarel Cohen, Lior Kamma, Aikaterini Niklanovits
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph , where , and an integer , the goal i…