Zobrazeno 1 - 10
of 587
pro vyhledávání: '"Golovach, P. A."'
Autor:
Fomin, Fedor V., Fraigniaud, Pierre, Golovach, Petr A., Montealegre, Pedro, Rapaport, Ivan, Todinca, Ioan
We show that for every first-order logic (FO) formula $\varphi$, and every graph class $\mathcal{G}$ of bounded expansion, there exists a distributed (deterministic) algorithm that, for every $n$-node graph $G\in\mathcal{G}$ of diameter $D$, decides
Externí odkaz:
http://arxiv.org/abs/2411.14825
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph $G$ and an integer $k\in\mathbb{N}$ as input, the goal is to determine whether we can perform at mos
Externí odkaz:
http://arxiv.org/abs/2411.13171
Autor:
Bentert, Matthias, Fomin, Fedor V., Golovach, Petr A., Korhonen, Tuukka, Lochet, William, Panolan, Fahad, Ramanujan, M. S., Saurabh, Saket, Simonov, Kirill
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Bj\"orklun
Externí odkaz:
http://arxiv.org/abs/2410.18878
In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut ca
Externí odkaz:
http://arxiv.org/abs/2410.17641
The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over long-term benefits, leading to suboptimal outcomes in various real-world
Externí odkaz:
http://arxiv.org/abs/2408.13675
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of points in R^d, an integer k, and a non-negative real r, our objective
Externí odkaz:
http://arxiv.org/abs/2407.08295
Autor:
Banik, Aritra, Fomin, Fedor V., Golovach, Petr A., Inamdar, Tanmay, Jana, Satyabrata, Saurabh, Saket
{\sc Vertex $(s, t)$-Cut} and {\sc Vertex Multiway Cut} are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representati
Externí odkaz:
http://arxiv.org/abs/2406.19134
We study the following Independent Stable Set problem. Let G be an undirected graph and M = (V(G),I) be a matroid whose elements are the vertices of G. For an integer k\geq 1, the task is to decide whether G contains a set S\subseteq V(G) of size at
Externí odkaz:
http://arxiv.org/abs/2404.03979
The connection between Hamiltonicity and the independence numbers of graphs has been a fundamental aspect of Graph Theory since the seminal works of the 1960s. This paper presents a novel algorithmic perspective on these classical problems. Our contr
Externí odkaz:
http://arxiv.org/abs/2403.05943
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) $n$-vertex graph $G$ along with $k$ terminal pairs $(s_1,t_1),(s_2,t_2),\ldots,(s_k,t_k)$. The
Externí odkaz:
http://arxiv.org/abs/2402.15348