4 papers
cs.DS2024
4/3-Approximation of Graphic TSP
Ali Ãivril
We describe a -approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweig…
cs.DS2024
3/2-Approximation for the Forest Augmentation Problem
Ali Ãivril
We describe a -approximation algorithm for the Forest Augmentation Problem (\textsf{FAP}), which is a special case of the Weighted 2-Edge-Connected Spanning Subgraph P…
cs.DS2024
9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
Ali Ãivril
We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio …
cs.DS2024
A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
Ali Ãivril
We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio both $\frac{4…