J. Nummenpalo

activity

20152019

most citedSparse Kneser graphs are Hamiltonian

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

collaborators

6 papers

cs.DS2019

Switches in Eulerian graphs

Ahad N. Zehmakan, Jerri Nummenpalo, Alexander Pilz +1

We show that the graph transformation problem of turning a simple graph into an Eulerian one by a minimum number of single edge switches is NP-hard. Further, we show that any simpl…

math.CO2017★ 10 cited

Sparse Kneser graphs are Hamiltonian

Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak

For integers $k \geq 1$ and $n \geq 2 k + 1$ , the Kneser graph $K (n, k)$ is the graph whose vertices are the $k$ -element subsets of ${1, \dots, n}$ and whose edges connect pairs of subs…

math.CO2017

A short proof of the middle levels theorem

Petr Gregor, Torsten Mütze, Jerri Nummenpalo

Consider the graph that has as vertices all bitstrings of length $2 n + 1$ with exactly $n$ or $n + 1$ entries equal to 1, and an edge between any two bitstrings that differ in exactly…

cs.DM2017

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems

Jean Cardinal, Jerri Nummenpalo, Emo Welzl

We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for s…

cs.DM2016

A constant-time algorithm for middle levels Gray codes

Torsten Mütze, Jerri Nummenpalo

For any integer $n \geq 1$ a middle levels Gray code is a cyclic listing of all $n$ -element and $(n + 1)$ -element subsets of ${1, 2, \dots, 2 n + 1}$ such that any two consecutive subset…

cs.DS2015

Efficient computation of middle levels Gray codes

Torsten Mütze, Jerri Nummenpalo

For any integer $n \geq 1$ a middle levels Gray code is a cyclic listing of all bitstrings of length $2 n + 1$ that have either $n$ or $n + 1$ entries equal to 1 such that any two consec…