Zobrazeno 1 - 10
of 121
pro vyhledávání: '"Suchý, Ondrej"'
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
Autor:
Bodlaender, Hans L., Bonnet, Édouard, Jaffke, Lars, Knop, Dušan, Lima, Paloma T., Milanič, Martin, Ordyniak, Sebastian, Pandey, Sukanya, Suchý, Ondřej
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on grap
Externí odkaz:
http://arxiv.org/abs/2301.10031
Autor:
Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Schierreich, Šimon, Suchý, Ondřej, Valla, Tomáš
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today's computation, we employ one of the most
Externí odkaz:
http://arxiv.org/abs/2207.01109
Autor:
Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Křišťan, Jan Matyáš, Suchý, Ondřej, Valla, Tomáš
Given an undirected graph $G=(V,E)$, vertices $s,t\in V$, and an integer $k$, Tracking Shortest Paths requires deciding whether there exists a set of $k$ vertices $T\subseteq V$ such that for any two distinct shortest paths between $s$ and $t$, say $
Externí odkaz:
http://arxiv.org/abs/2202.11927
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
Autor:
Červený, Radovan, Suchý, Ondřej
Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order t
Externí odkaz:
http://arxiv.org/abs/2111.05896
Publikováno v:
In Journal of Computer and System Sciences September 2024 144
Autor:
Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Křišťan, Jan Matyáš, Suchý, Ondřej, Valla, Tomáš
Consider a vertex-weighted graph $G$ with a source $s$ and a target $t$. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from $s$ to $t$ is unique. In this work, we derive a
Externí odkaz:
http://arxiv.org/abs/2108.01430
In this paper we study the kernelization of the $d$-Path Vertex Cover ($d$-PVC) problem. Given a graph $G$, the problem requires finding whether there exists a set of at most $k$ vertices whose removal from $G$ results in a graph that does not contai
Externí odkaz:
http://arxiv.org/abs/2107.12245
Inspired by the famous Target Set Selection problem, we propose a new discrete model for simultaneously spreading several opinions within a social network and perform an initial study of its complexity. Here, we are given a social network, a seed-set
Externí odkaz:
http://arxiv.org/abs/2105.10184