, We denote by A the set N \ A, and for any positive integer k we set kA = {k × a | a ? A}. An A-ear-decomposition of a graph is an ear decomposition in which all ears have length in A. Similarly, an A-handle-decomposition of a digraph is a handle decomposition in which all handles have length in A. Note that an A-ear-decomposition (resp. A-handle-decomposition) of a graph (resp. digraph) can be seen as an ear decomposition (resp. handle decomposition) with no ear (resp. handle) with length in A. In view of all our results, Let A be a set of positive integers

Question: Does G admit an A-ear-decomposition ?, A graph G ,

Question: Does D admit an A-handle-decomposition ? It would be nice to characterize the graphs (resp. digraphs) for which A-EAR-DECOMPOSITION (resp. A-HANDLE-DECOMPOSITION) is polynomial-time solvable. Below is an easy lemma ,

Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph, SIAM J. Discrete Math, vol.14, issue.2, pp.170-180, 2001. ,

Worst-case analysis of a new heuristic for the travelling salesman problem, Graduate School of Industrial Administration, 1976. ,

Conservtive weightings and ear-decompositions of graphs, Combinatorica, vol.13, pp.65-81, 1993. ,

Some simplified NP-complete graph problems, Theor. Comput. Sci, vol.1, issue.3, pp.237-267, 1976. ,

A randomized rounding approach to the traveling salesman problem, Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pp.550-559, 2011. ,

Biconnectivity approximations and graph carvings, Journal of the ACM, vol.41, issue.2, pp.214-235, 1994. ,

On the hardness of global and local approximation, Algorithm Theory -SWAT'96, pp.88-99, 1996. ,

A note on factor-critical graphs, Studia Sci. Math. Hungar, vol.7, pp.279-280, 1972. ,

Approximating graphic TSP by matchings, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp.560-569, 2011. ,

, Graphic TSP. Theory of Computing Systems, vol.13, pp.640-657, 2014.

URL : https://hal.archives-ouvertes.fr/hal-00678172

A theorem on graphs with an application to a problem on traffic control, Amer. Math. Mon, vol.46, pp.281-283, 1939. ,

Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Combinatorica, 2014. ,

Approximating the minimum strongly connected subgraph via a matching lower bound, Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.417-426, 2001. ,