1 citations · 1 across the 3 of their papers we have counts for
12 papers
A Note on Coloring -free graphs with a
Martin Koutecký
Even-hole-free graphs are a graph class of much interest. Foley et al. [Graphs Comb. 36(1): 125-138 (2020)] have recently studied -free graphs, which form a subcl…
Uniform and Monotone Line Sum Optimization
Martin Koutecky, Shmuel Onn
The {\em line sum optimization problem} asks for a -matrix minimizing the sum of given functions evaluated at its row and column sums. We show that the {\em uniform} problem…
Opinion Diffusion and Campaigning on Society Graphs
Piotr Faliszewski, Rica Gonen, Martin Koutecký +1
We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting the clusters. Our mode…
Multitype Integer Monoid Optimization and Applications
Dušan Knop, Martin Koutecký, Asaf Levin +2
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 19…
Voting and Bribing in Single-Exponential Time
Dušan Knop, Martin Koutecký, Matthias Mnich
We introduce a general problem about bribery in voting systems. In the -Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired…
Approximating Max-Cut under Graph-MSO Constraints
Martin Koutecký, Jon Lee, Viswanath Nagarajan +1
We consider the max-cut and max--cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of…