Zobrazeno 1 - 10
of 703
pro vyhledávání: '"Golovach, Petr"'
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
According to the classic Chv{\'{a}}tal's Lemma from 1977, a graph of minimum degree $\delta(G)$ contains every tree on $\delta(G)+1$ vertices. Our main result is the following algorithmic "extension" of Chv\'{a}tal's Lemma: For any $n$-vertex graph $
Externí odkaz:
http://arxiv.org/abs/2310.09678
Autor:
Didimo, Walter, Fomin, Fedor V., Golovach, Petr A., Inamdar, Tanmay, Kobourov, Stephen, Sieper, Marie Diana
A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of
Externí odkaz:
http://arxiv.org/abs/2308.15635