中国科学院机构知识库网格系统: Covering Triangles in Edge-Weighted Graphs

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
语种	英语
WOS记录号	WOS:000434050300010
出版者	SPRINGER
源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.

入库方式： OAI收割

来源：数学与系统科学研究院

下载0

Covering Triangles in Edge-Weighted Graphs

其他版本