, 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

, A-Ear-Decomposition Input: A graph G. Question: Does G admit an A-ear-decomposition ?

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, Decomposition Input: A digraph D ,

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. ,

DOI : 10.1016/0304-3975(76)90059-1

URL : https://doi.org/10.1016/0304-3975(76)90059-1

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. ,

DOI : 10.1145/129712.129786

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. ,

13 9-approximation for Graphic TSP. Theory of Computing Systems, vol.55, 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. ,