
On (Coalitional) ExchangeStable Matching
We study (coalitional) exchange stability, which Alcalde [Economic Desig...
read it

Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
read it

Fractional Matchings under Preferences: Stability and Optimality
We thoroughly study a generalized version of the classic Stable Marriage...
read it

The Complexity of Connectivity Problems in ForbiddenTransition Graphs and EdgeColored Graphs
The notion of forbiddentransition graphs allows for a robust generaliza...
read it

Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
read it

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
read it

Optimal Discretization is Fixedparameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
read it

A Double Exponential Lower Bound for the Distinct Vectors Problem
In the (binary) Distinct Vectors problem we are given a binary matrix A ...
read it

Cluster Editing parameterized above the size of a modificationdisjoint P_3 packing is paraNPhard
Given a graph G=(V,E) and an integer k, the Cluster Editing problem asks...
read it

Packing directed circuits quarterintegrally
The celebrated ErdősPósa theorem states that every undirected graph tha...
read it

Matchings under Preferences: Strength of Stability and Tradeoffs
We propose two solution concepts for matchings under preferences: robust...
read it

Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Given an undirected graph G=(V,E) the NPhard Strong Triadic Closure (ST...
read it

Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
A fundamental graph problem is to recognize whether the vertex set of a ...
read it

A Note on Clustering Aggregation
We consider the clustering aggregation problem in which we are given a s...
read it

On Computing Centroids According to the pNorms of Hamming Distance Vectors
In this paper we consider the pNorm Hamming Centroid problem which asks...
read it

Efficient Algorithms for Measuring the Funnellikeness of DAGs
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funn...
read it

Computational Complexity Aspects of Point Visibility Graphs
A point visibility graph is a graph induced by a set of points in the pl...
read it

The Parameterized Complexity of Centrality Improvement in Networks
The centrality of a vertex v in a network intuitively captures how impor...
read it

A Parameterized View on MultiLayer Cluster Editing
In classical Cluster Editing we seek to transform a given graph into a d...
read it

How hard is it to satisfy (almost) all roommates?
The classical Stable Roommates problem (which is a nonbipartite general...
read it
Manuel Sorge
is this you? claim profile