2 citations · 3 across the 5 of their papers we have counts for
5 papers
A -Approximation Algorithm for Flexible Graph Connectivity
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan +1
We present a -approximation algorithm for the Flexible Graph Connectivity problem [AHM20] via a reduction to the minimum cost -out -arborescence problem.
A -Approximation Algorithm for the Minimum -Edge Connected Multisubgraph Problem in the Half-Integral Case
S. Boyd, J. Cheriyan, R. Cummings +4
Given a connected undirected graph on vertices, and non-negative edge costs , the 2ECM problem is that of finding a -edge~connected spanning multisubgraph of $\…
The Salesman's Improved Tours for Fundamental Classes
Sylvia Boyd, András Sebö
Finding the exact integrality gap for the LP relaxation of the metric Travelling Salesman Problem (TSP) has been an open problem for over thirty years, with little progress mad…
Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph Problem
Sylvia Boyd, Philippe Legault
Given a complete graph with non-negative edge costs , the problem is that of finding a 2-edge connected spanning multi-subgraph of $K_{n}…
The traveling salesman problem on cubic and subcubic graphs
Sylvia Boyd, René Sitters, Suzanne van der Ster +1
We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relati…