Covering Triangles in Edge-Weighted Graphs

doi:10.1007/s00224-018-9860-7

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Covering Triangles in Edge-Weighted Graphs
	Chen, Xujin1,2 ; Diao, Zhuo 3; Hu, Xiaodong1,2 ; Tang, Zhongzheng 1,2,4
刊名	THEORY OF COMPUTING SYSTEMS
	2018-08-01
卷号	62 期号:6 页码:1525-1552
关键词	Triangle cover Triangle packing Linear 3-uniform hypergraphs Combinatorial algorithms
ISSN号	1432-4350
DOI	10.1007/s00224-018-9860-7
英文摘要	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.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000434050300010
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/30414]
专题	应用数学研究所
通讯作者	Diao, Zhuo
作者单位	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
推荐引用方式 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.