{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q484552","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q484552","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q484552","kernelVersion":"v1","immutable":true,"modified":"2026-03-25T14:45:02Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q484552","name":"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","headline":"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","description":"scientific article; zbMATH DE number 6384173","url":"https://portal.mardi4nfdi.de/entity/Q484552","datePublished":"2015-01-07","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q210363"},{"@id":"https://portal.mardi4nfdi.de/entity/Q226822"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q168579"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/S00493-014-2960-3","url":"https://doi.org/10.1007/S00493-014-2960-3"},"sameAs":["https://doi.org/10.1007/S00493-014-2960-3"],"comment":"Given a graph \\(G=(V,E)\\), let \\(2G\\) denote the graph arising from \\(G\\) by doubling all its edges. For an even cardinality set \\(T \\subseteq V\\), a \\(T\\)-join is a set \\(F \\subseteq E\\) such that in the graph \\((V,F)\\), \\(T\\) is the set of vertices with odd degree. A \\(T\\)-tour in \\(G\\) is a \\(T\\)-join \\(F\\) in \\(2G\\) such that \\((V,F)\\) is connected. Given a connected graph \\(G\\) and an even cardinality set \\(T \\subseteq V\\), the minimum \\(T\\)-tour problem is to find a \\(T\\)-tour in \\(G\\) of minimum cardinality \\(\\mathrm{opt}(G,T)\\). If \\(T=\\emptyset\\), \\(F\\) is called a tour, and the minimum \\(T\\)-tour problem is the well-known graph-TSP with optimal value \\(\\mathrm{opt}(G)\\). If \\(| T| =2\\), say \\(T=\\{s,t\\}\\), the \\(s\\)-\\(t\\)-path graph TSP arises as a further special case. Finally, for a given \\(2\\)-edge-connected graph \\(G\\), the \\(2\\)-edge-connected subgraph problem 2ECSS is to find a \\(2\\)-edge-connected spanning subgraph of \\(G\\) with minimum number of edges \\(\\mathrm{opt}_{\\text{2EC}}(G)\\). \\ The authors provide polynomial-time algorithms with approximation ratio \\(7/5\\) for the graph-TSP, \\(3/2\\) for the minimum \\(T\\)-tour problem (including the \\(s,t\\)-path graph-TSP), and \\(4/3\\) for the 2ECSS-problem. Based on a special kind of ear-decomposition optimized using forest representations of hypergraphs, the four main constructions can be resumed as follows:\\newline i) a \\(T\\)-tour of cardinality at most \\(3/2 \\mathrm{opt}(G,T)+1/2\\varphi-\\pi\\) (and at most \\(3/2 \\mathrm{opt}(G)-\\pi\\) if \\(T=\\emptyset\\)) can be constructed in polynomial time, where \\(\\varphi\\) and \\(\\pi\\) are the number of even and of pendant ears in a suitable ear-decomposition. For the three approximation algorithms and the case when \\(\\pi\\) is small, three different second constructions are presented: \\newline ii) an inductive construction with respect to the ear-decomposition provides a \\(T\\)-tour of cardinality at most \\(3/2 \\mathrm{opt}(G,T)-1/2\\varphi+\\pi\\), so that the smaller of the two \\(T\\)-tours has cardinality at most \\(3/2 \\mathrm{opt}(G,T)\\); \\newline iii) if \\(T=\\emptyset\\), the second construction applies a lemma to the ear-decomposition, obtaining the bound \\(4/3 \\mathrm{opt}(G)+2/3\\pi\\); \\newline iv) a simple induction with respect to the number of ears provides the bound \\(5/4 \\mathrm{opt}_{\\text{2EC}}(G)+1/2\\pi\\) for 2ECSS.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q5415521"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1102297"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3009751"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3840351"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2706198"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5894461"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3675933"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5684698"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4766817"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2367443"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3085455"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2488197"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4115165"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1180833"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4299007"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4091971"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5611639"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4106238"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1088987"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5494987"},{"@id":"https://portal.mardi4nfdi.de/entity/Q582215"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2904746"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5494986"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4697080"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5845425"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4911537"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4333930"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3885519"}]},"provenance":{"prov:generatedAtTime":"2026-03-25T14:45:02Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}