6 citations · 12 across the 11 of their papers we have counts for
4 papers · 1 filter
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…
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets and such that and satisfy properties an…
On Computing Centroids According to the -Norms of Hamming Distance Vectors
Jiehua Chen, Danny Hermelin, Manuel Sorge
In this paper we consider the -Norm Hamming Centroid problem which asks to determine whether some given binary strings have a centroid with a bound on the -norm of its Hammin…
Efficient Algorithms for Measuring the Funnel-likeness of DAGs
Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier +1
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees f…