Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Hamm, Thekla"'
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function $u$ that took into account distances in a given social network. In this paper, w
Externí odkaz:
http://arxiv.org/abs/2312.07632
Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dyna
Externí odkaz:
http://arxiv.org/abs/2312.08385
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a co
Externí odkaz:
http://arxiv.org/abs/2312.07043
Autor:
Chalermsook, Parinya, Fomin, Fedor, Hamm, Thekla, Korhonen, Tuukka, Nederlof, Jesper, Orgo, Ly
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph $G$)
Externí odkaz:
http://arxiv.org/abs/2307.01341
Courcelle's theorem and its adaptations to cliquewidth have shaped the field of exact parameterized algorithms and are widely considered the archetype of algorithmic meta-theorems. In the past decade, there has been growing interest in developing par
Externí odkaz:
http://arxiv.org/abs/2305.02056
The generic homomorphism problem, which asks whether an input graph $G$ admits a homomorphism into a fixed target graph $H$, has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the runnin
Externí odkaz:
http://arxiv.org/abs/2210.06845
Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEMPORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER(or $\Delta$-TVC for time-windows of a fixed-length $\Delta$) have been
Externí odkaz:
http://arxiv.org/abs/2204.04832
Autor:
Hamm, Thekla, Hliněný, Petr
Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predr
Externí odkaz:
http://arxiv.org/abs/2202.13635
Publikováno v:
Artificial Intelligence 325 (2023) 104017:1-20
Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the m
Externí odkaz:
http://arxiv.org/abs/2202.09210
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms f
Externí odkaz:
http://arxiv.org/abs/2109.14610