1 citations · 1 across the 5 of their papers we have counts for
7 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 and…
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…
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)…
Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
Katrin Casel, Tobias Friedrich, Davis Issac +2
In the 1970s, Győri and Lovász showed that for a -connected -vertex graph, a given set of terminal vertices and natural numbers satisfying…
Connected -partition of -connected graphs and -claw-free graphs
Ralf Borndörfer, Katrin Casel, Davis Issac +3
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road ne…
Balanced Crown Decomposition for Connectivity Constraints
Katrin Casel, Tobias Friedrich, Davis Issac +2
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular model…