Frank Sommer

activity

20192026

P_{3}

s by Deleting Few Edges

4 citations · 10 across the 13 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021

Preventing Small $(s, t)$ -Cuts by Protecting Edges

Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz +1

We introduce and study Weighted Min $(s, t)$ -Cut Prevention, where we are given a graph $G = (V, E)$ with vertices $s$ and $t$ and an edge cost function and the aim is to choose an edg…

cs.DS2021★ 2 cited

Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

Nils Jakob Eckstein, Niels Grüttemeier, Christian Komusiewicz +1

We study the computational complexity of $c$ -Colored $P_{ℓ}$ Deletion and $c$ -Colored $C_{ℓ}$ Deletion. In these problems, one is given a $c$ -edge-colored graph and wants to dest…

cs.DS2021

Essentially Tight Kernels for (Weakly) Closed Graphs

Tomohiro Koana, Christian Komusiewicz, Frank Sommer

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closu…

Preventing Small (s,t)-Cuts by Protecting Edges

Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

Essentially Tight Kernels for (Weakly) Closed Graphs

Preventing Small $(s, t)$ -Cuts by Protecting Edges