KMS Of Academy of mathematics and systems sciences, CAS
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 |
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 | 应用数学研究所 |
Affiliation | 1.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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment