DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS

doi:10.1137/17M1147676

CSpace > 应用数学研究所

	DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS
	Chen, Xujin1,2 ; Zang, Wenan 3; Zhao, Qiulan 4
	2019
发表期刊	SIAM JOURNAL ON OPTIMIZATION
ISSN	1052-6234
卷号	29 期号:1 页码:240-261
摘要	Given a multigraph G = (V, E) with a positive rational weight w(e) on each edge e, the weighted density problem (WDP) is to find a subset U of V, with vertical bar U vertical bar >= 3 and odd, that maximizes 2w(U)/(vertical bar U vertical bar - 1), where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize 1(T) x subject to Ax = w, x >= 0, where A is the edge-matching incidence matrix of G. These two problems are closely related to the celebrated Goldberg-Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when w(e) = 1 for all edges e, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327-357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring.
关键词	multigraph density matching fractional edge-coloring algorithm
DOI	10.1137/17M1147676
语种	英语
资助项目	NSF of China[11801266] ; Research Grants Council of Hong Kong ; Fundamental Research Funds for the Central Universities[14380020]
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000462593800010
出版者	SIAM PUBLICATIONS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/34216
专题	应用数学研究所
通讯作者	Zhao, Qiulan
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China 3.Univ Hong Kong, Dept Math, Hong Kong, Peoples R China 4.Nanjing Univ, Dept Math, Nanjing 210093, Jiangsu, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Zang, Wenan,Zhao, Qiulan. DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS[J]. SIAM JOURNAL ON OPTIMIZATION,2019,29(1):240-261.
APA	Chen, Xujin,Zang, Wenan,&Zhao, Qiulan.(2019).DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS.SIAM JOURNAL ON OPTIMIZATION,29(1),240-261.
MLA	Chen, Xujin,et al."DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS".SIAM JOURNAL ON OPTIMIZATION 29.1(2019):240-261.