A PTAS for triangle-free 2-matching
Abstract In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) . Our goal is to compute a maximum-cardinality $$M\subseteq E$$ M ⊆ E satisfying the following properties: (1) at most two edges of M are incident on each node (i.e., M is a 2-matching) and (2) M does no...
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
· Mathematical Programming · 0 citations