3 papers
cs.DS2026
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
Yusuke Kobayashi, Afrouz Jabal Ameli, Takashi Noguchi
In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph , and the objective is to find a 2-vertex-connected spanning subgraph of w…
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…