CSpace  > 应用数学研究所
Covering Triangles in Edge-Weighted Graphs
Chen, Xujin1,2; Diao, Zhuo3; Hu, Xiaodong1,2; Tang, Zhongzheng1,2,4
2018-08-01
Source PublicationTHEORY OF COMPUTING SYSTEMS
ISSN1432-4350
Volume62Issue:6Pages:1525-1552
AbstractLet 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.
KeywordTriangle cover Triangle packing Linear 3-uniform hypergraphs Combinatorial algorithms
DOI10.1007/s00224-018-9860-7
Language英语
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Mathematics
WOS IDWOS:000434050300010
PublisherSPRINGER
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/30415
Collection应用数学研究所
Corresponding AuthorDiao, Zhuo
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China
2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China
3.Cent Univ Finance & Econ, Sch Stat & Math, Beijing, Peoples R China
4.City Univ Hong Kong, Dept Comp Sci, Hksar, Kowlon Tong, Peoples R China
Recommended Citation
GB/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
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.