2 citations · 3 across the 8 of their papers we have counts for
10 papers
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…
Optimal Padded Decomposition For Bounded Treewidth Graphs
Arnold Filtser, Tobias Friedrich, Davis Issac +4
A -padded decomposition of an edge-weighted graph is a stochastic decomposition into clusters of diameter at most such that for every vertex , th…
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)…
On the Giant Component of Geometric Inhomogeneous Random Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +2
In this paper we study the threshold model of \emph{geometric inhomogeneous random graphs} (GIRGs); a generative random graph model that is closely related to \emph{hyperbolic rand…
Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem
Samuel Baguley, Tobias Friedrich, Aneta Neumann +3
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary al…
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich, Davis Issac, Nikhil Kumar +2
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth- graph, there exists a (fraction…
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…
Analysis of a Gray-Box Operator for Vertex Cover
Samuel Baguley, Tobias Friedrich, Timo Kötzing +3
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by int…
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…