3 papers
cs.DS2026
A PTAS for Weighted Triangle-free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Yusuke Kobayashi +1
In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e…
cs.DS2024
On the Bidirected Cut Relaxation for Steiner Forest
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of ver…
cs.DS2023
A PTAS for Triangle-Free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph . Our goal is to compute a maximum-cardinality satisfying the following pr…