CSpace  > 应用数学研究所
 Covering Triangles in Edge-Weighted Graphs Chen, Xujin1,2 ; Diao, Zhuo3; Hu, Xiaodong1,2 ; Tang, Zhongzheng1,2,4 2018-08-01 Source Publication THEORY OF COMPUTING SYSTEMS ISSN 1432-4350 Volume 62Issue:6Pages:1525-1552 Abstract Let G = (V, E) be a simple graph and assign each edge e a E a positive integer weight w(e). A subset of E that intersects every triangle of G is called a triangle cover of (G, w), and its weight is the total weight of its edges. A collection of triangles in G (repetition allowed) is called a triangle packing of (G, w) if each edge e a E appears in at most w(e) members of the collection. Let tau (t) (G, w) and nu (t) (G, w) denote the minimum weight of a triangle cover and the maximum cardinality of a triangle packing of (G, w), respectively. Generalizing Tuza's conjecture for unit weight, Chapuy et al. conjectured that tau (t) (G, w)/nu (t) (G, w) ae 2 holds for every simple graph G and every . In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding triangle covers of small weights. These algorithms imply new sufficient conditions for the conjecture of Chapuy et al. More precisely, given (G, w), suppose that all edges of G are covered by the set consisting of edge sets of triangles in G. Let and denote the weighted numbers of edges and triangles in (G, w), respectively. We show that a triangle cover of (G, w) of weight at most 2 nu (t) (G, w) can be found in strongly polynomial time if one of the following conditions is satisfied: (i).t(G, w)/vertical bar TG vertical bar w >= 1/3, (ii).t(G, w)/vertical bar E vertical bar w >= 1/4, (iii) vertical bar E vertical bar(w)/vertical bar TG vertical bar(w) >= 2. Keyword Triangle cover Triangle packing Linear 3-uniform hypergraphs Combinatorial algorithms DOI 10.1007/s00224-018-9860-7 Language 英语 WOS Research Area Computer Science ; Mathematics WOS Subject Computer Science, Theory & Methods ; Mathematics WOS ID WOS:000434050300010 Publisher SPRINGER Citation statistics Document Type 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/30415 Collection 应用数学研究所 Corresponding Author Diao, Zhuo Affiliation 1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China3.Cent Univ Finance & Econ, Sch Stat & Math, Beijing, Peoples R China4.City Univ Hong Kong, Dept Comp Sci, Hksar, Kowlon Tong, Peoples R China Recommended CitationGB/T 7714 Chen, Xujin,Diao, Zhuo,Hu, Xiaodong,et al. Covering Triangles in Edge-Weighted Graphs[J]. THEORY OF COMPUTING SYSTEMS,2018,62(6):1525-1552. APA Chen, Xujin,Diao, Zhuo,Hu, Xiaodong,&Tang, Zhongzheng.(2018).Covering Triangles in Edge-Weighted Graphs.THEORY OF COMPUTING SYSTEMS,62(6),1525-1552. MLA Chen, Xujin,et al."Covering Triangles in Edge-Weighted Graphs".THEORY OF COMPUTING SYSTEMS 62.6(2018):1525-1552.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Google Scholar Similar articles in Google Scholar [Chen, Xujin]'s Articles [Diao, Zhuo]'s Articles [Hu, Xiaodong]'s Articles Baidu academic Similar articles in Baidu academic [Chen, Xujin]'s Articles [Diao, Zhuo]'s Articles [Hu, Xiaodong]'s Articles Bing Scholar Similar articles in Bing Scholar [Chen, Xujin]'s Articles [Diao, Zhuo]'s Articles [Hu, Xiaodong]'s Articles Terms of Use No data! Social Bookmark/Share