2 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
Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem
Yusuke Kobayashi, Takashi Noguchi
A triangle-free (simple) 2-matching is an edge set that has at most edges incident to each vertex and contains no cycle of length . For the problem of finding a maximum card…