A 4/3-approximation for TSP on cubic 3-edge-connected graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A 4/3-approximation for TSP on cubic 3-edge-connected graphs

Authors:	Nishita Agarwal Naveen Garg Swati Gupta

Institution:	1. Facebook, NY, United States;2. Indian Institute of Technology, Delhi, India;3. Simons Institute for the Theory of Computing, UC Berkeley, United States

Abstract:	For a 3-edge-connected cubic graph $G = (V, E)$ , we give an algorithm to construct a connected Eulerian subgraph of $2 G$ using at most $? 4 \| V \| ∕ 3 ?$ edges.

Keywords:	Traveling salesman problem Cubic graphs 4/3 approximation Cycle covers
本文献已被 ScienceDirect 等数据库收录！