6 papers
The realization graph of every degree sequence has a Hamilton path
Petr Hladík, Jiří Fink
For a degree sequence , the realization graph is the graph whose vertices are the labeled realizations of , two of which are adjacent if they differ by a s…
Faster and simpler traversal of 0/1-polytopes
Jiří Fink, Petr Hladík, Arturo Merino +2
Recently, Merino and Mütze (FOCS'23+SICOMP'24) presented an algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope , where …
Minimum maximal matchings in permutahedra
Sofia Brenner, Jiří Fink, Hung. P. Hoang +2
We prove that the minimal size of a maximal matching in the permutahedron is asymptotically . On the one hand, we obtain a lower bound $M(π_n) \ge n! (n-1) / (…
Matchings in hypercubes extend to long cycles
Jiří Fink, Torsten Mütze
The -dimensional hypercube graph has as vertices all subsets of , and an edge between any two sets that differ in a single element. The Ruskey-Savage conje…
A New Arc-Routing Algorithm Applied to Winter Road Maintenance
Jiří Fink, Martin Loebl, Petra Pelikánová
This paper studies large scale instances of a fairly general arc-routing problem as well as incorporate practical constraints in particular coming from the scheduling problem of th…
Arc-routing for winter road maintenance
Jiří Fink, Martin Loebl
The arc-routing problems are known to be notoriously hard. We study here a natural arc-routing problem on trees and more generally on bounded tree-width graphs and surprisingly sho…