81 citations · 388 across the 46 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
math.CO2012
A tighter Erdös-Pósa function for long cycles
Samuel Fiorini, Audrey Herinckx
We prove that there exists a bivariate function f with f(k,l) = O(l k log k) such that for every naturals k and l, every graph G has at least k vertex-disjoint cycles of length at…
math.CO2012★ 9 cited
Excluded Forest Minors and the Erdős-Pósa Property
Samuel Fiorini, Gwenaël Joret, David R. Wood
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph as a minor has the so-called Erdős-Pósa property; namely, there exists…
cs.CC2012★ 40 cited
Approximation Limits of Linear Programs (Beyond Hierarchies)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta +1
We develop a framework for approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields un…