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
Source Publication	THEORY OF COMPUTING SYSTEMS
ISSN	1432-4350
Volume	62 Issue:6 Pages: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 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.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院数学与系统科学研究院机构知识库