Showing cs.DMShow all
3 papers · 1 filter
cs.DM2023
A note on local search for hitting sets
Zdeněk Dvořák
Let be a property of pairs , where is a graph and . In the \emph{minimum -hitting set problem}, given an input graph , we want to find a small…
cs.DM2023
An efficient implementation and a strengthening of Alon-Tarsi list coloring method
Zdeněk Dvořák
As one of the first applications of the polynomial method in combinatorics, Alon and Tarsi gave a way to prove that a graph is choosable (colorable from any lists of prescribed siz…
cs.DM2021
Approximation metatheorems for classes with bounded expansion
Zdeněk Dvořák
We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than the previously k…