2 citations · 2 across the 5 of their papers we have counts for
4 papers · 1 filter
Improved Erdős-Pósa inequalities for odd cycles in planar graphs
Luise Puhlmann, Niklas Schlomberg
In an undirected graph, the odd cycle packing number is the maximum number of pairwise vertex-disjoint odd cycles. The odd cycle transversal number is the minimum number of vertice…
Curves on the torus with few intersections
Igor Balla, Marek Filakovský, Bartłomiej Kielak +2
Aougab and Gaster [Math. Proc. Cambridge Philos. Soc. 174 (2023), 569-584] proved that any set of simple closed curves on the torus, where any two are non-homotopic and intersect a…
An improved integrality gap for disjoint cycles in planar graphs
Niklas Schlomberg
We present a new greedy rounding algorithm for the Cycle Packing Problem for uncrossable cycle families in planar graphs. This improves the best-known upper bound for the integrali…
Packing cycles in planar and bounded-genus graphs
Niklas Schlomberg, Hanjo Thiele, Jens Vygen
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here di…