W. Kern

activity

20162021

collaborators

5 papers

math.CO2021

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Walter Kern, Barnaby Martin, Daniël Paulusma +2

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We deter…

cs.GT2018

Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value

Frits Hof, Walter Kern, Sascha Kurz +2

A simple game $(N, v)$ is given by a set $N$ of $n$ players and a partition of~ $2^{N}$ into a set~ $L$ of losing coalitions~ $L$ with value $v (L) = 0$ that is closed under takin…

cs.DS2018

Contracting to a Longest Path in H-Free Graphs

Walter Kern, Daniel Paulusma

We prove two dichotomy results for detecting long paths as patterns in a given graph. The NP-hard problem Longest Induced Path is to determine the longest induced path in a graph.…

cs.GT2018

Simple Games versus Weighted Voting Games

Frits Hof, Walter Kern, Sascha Kurz +1

A simple game $(N, v)$ is given by a set $N$ of $n$ players and a partition of $2^{N}$ into a set $L$ of losing coalitions $L$ with value $v (L) = 0$ that is closed under takin…

cs.GT2016

Note on VCG vs. Price Raising for Matching Markets

Walter Kern, Bodo Manthey, Marc Uetz

In \cite{EK10} the use of VCG in matching markets is motivated by saying that in order to compute market clearing prices in a matching market, the auctioneer needs to know the true…