3 papers
cs.DS2020
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
Given an undirected graph and integers and , the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most edges in to obtain a graph that has a…
cs.DS2018
Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz +1
Given an undirected graph the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as \emph{weak} and \emph{strong} such that at most edges a…
cs.DS2018
On the Relation of Strong Triadic Closure and Cluster Deletion
Niels Grüttemeier, Christian Komusiewicz
We study the parameterized and classical complexity of two related problems on undirected graphs . In Strong Triadic Closure we aim to label the edges in as strong and…