|
Abstract: |
Given a multigraph G = (V, E), an edge cover of G is subset F of E such that each vertex of G is incident to at least one edge in F. The edge cover packing problem (ECPP) is to find a coloring of edges of G using the maximum number of colors in such a way that at each vertex all colors occur. It is easy to see that each color class induces an edge cover. The ECPP can be regarded as the dual version of the edge-coloring problem, and is also NP-hard in general. In this paper, we consider its (weighted) fractional version. Let A be the edge-edge cover incidence matrix of G. The weighted fractional edge cover packing problem (WECPP), can be formulated as the following linear program
Maximize 1Tx
subject to Ax = w
x ≥ 0,
where w = (w(e) : e ∈ E), and w(e) is a positive rational weight associated with each edge e of G. We will present a strongly polynomial-time algorithm for solving this problem.
Affiliation: 赵秋兰，南京大学数学系助理研究员。赵秋兰分别于2009年和2012年在郑州大学数学系获得学士和硕士学位，于2017年在香港大学获得博士学位，毕业后加入南京大学数学系工作至今。主要研究方向包括多面体组合，图论和排序论，目前主持国家自然科学基金培育项目一项以及国家自然科学基金青年项目一项。 |