Covering Triangles in Edge-Weighted Graphs

doi:10.1007/s00224-018-9860-7

CSpace > 应用数学研究所

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