Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Grout, Logan"'
We present approximation algorithms for network design problems in some models related to the $(p,q)$-FGC model. Adjiashvili, Hommelsheim and M\"uhlenthaler introduced the model of Flexible Graph Connectivity that we denote by FGC. Boyd, Cheriyan, Ha
Externí odkaz:
http://arxiv.org/abs/2211.09747
We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson
Externí odkaz:
http://arxiv.org/abs/2209.11209
The $k$-Steiner-2NCS problem is as follows: Given a constant $k$, and an undirected connected graph $G = (V,E)$, non-negative costs $c$ on $E$, and a partition $(T, V-T)$ of $V$ into a set of terminals, $T$, and a set of non-terminals (or, Steiner no
Externí odkaz:
http://arxiv.org/abs/2206.11807
Our motivation is to improve on the best approximation guarantee known for the problem of finding a minimum-cost 2-node connected spanning subgraph of a given undirected graph with nonnegative edge costs. We present an LP (Linear Programming) relaxat
Externí odkaz:
http://arxiv.org/abs/2111.07481
Autor:
Grout, Logan, Moore, Benjamin
We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k + \frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests $C_{1},\ldots,C_{k+1}$ such that there is an $i$ such that for every connecte
Externí odkaz:
http://arxiv.org/abs/1905.02600
Autor:
Grout, Logan, Moore, Benjamin
We prove that for $k \in \mathbb{N}$ and $d \leq 2k+2$, if a graph has maximum average degree at most $2k + \frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests, where one of the pseudoforests has all connected components having at most $d
Externí odkaz:
http://arxiv.org/abs/1904.12435
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Grout, Logan, Moore, Benjamin
Publikováno v:
In Journal of Combinatorial Theory, Series B November 2020 145:433-449
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Boyd, Sylvia, Cheriyan, Joseph, Cummings, Robert, Grout, Logan, Ibrahimpur, Sharat, Szigeti, Zoltán, Wang, Lu
Publikováno v:
APPROX 2020
APPROX 2020, Aug 2020, Seattle, United States. pp.61:1-61:12
APPROX 2020, Aug 2020, Seattle, United States. pp.61:1-61:12
Given a connected undirected graph $\bar{G}$ on $n$ vertices, and non-negative edge costs $c$, the 2ECM problem is that of finding a $2$-edge~connected spanning multisubgraph of $\bar{G}$ of minimum cost. The natural linear program (LP) for 2ECM, whi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::656b0e948e1bf0b5d2218689acd16e64
http://arxiv.org/abs/2008.03327
http://arxiv.org/abs/2008.03327