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
Polynomial Kernels with Reachability for Weighted -Matroid Intersection
Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi +1
This paper studies randomized polynomial kernelization for the weighted -matroid intersection problem. While the problem is known to have a kernel of size wher…
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…