Co-density and fractional edge cover packing
Co-density and fractional edge cover packing
复制标题
同密度和分数边缘覆盖封装
DOI：
10.1007/s10878-020-00535-x
复制
发表时间：
2020-02
影响因子：
1
通讯作者：
Jiajun Sang
中科院分区：
文献类型：
--
作者：
Qiulan Zhao;陈智斌;Jiajun Sang
给定一个重图G=(V，E)G=(V，E)，图G上的边覆盖包装问题(ECPP)是用最大颜色数求出图G的边的一个着色，使得所有的颜色都出现在每个顶点上。ECPP可以表示为一个整数规划，并且通常是NP难的。在本文中，我们考虑了分数边覆盖装箱问题，即ECPP的LP松弛。我们关注更一般的加权设置，加权分数边覆盖装箱问题(WFECPP)，它可以被表示为如下的线性规划：最大Tx服从&Ax≤wx≥0，最大化1Tx服从Ax≤Wx≥0，其中A是G的边覆盖关联矩阵，w=(w(E)：E∈E)w=(w(E)：E∈E)，w(E)是G的每个边e上的正有理权重，与加权分数边覆盖装箱问题密切相关，找到一个子集S⊆V S⊆V满足|S|≥3|S|≥3且奇数，使得2w(E^+(S)|S|+12 w(E+(S))|S|++1是最小化的，其中E^+(S)E+(S)是G的所有边的集合，至少有一端在S，w(E^+(S))w(E+(S))是E^+(S)E+(AC.105)中所有边的权重之和。我们给出了精确求解这两个问题的多项式组合算法。
Given a multigraph G=(V, E) G=(V, E), the edge cover packing problem (ECPP) on G is to find a coloring of edges of G using the maximum number of colors such that at each vertex all colors occur. ECPP can be formulated as an integer program and is NP-hard in general. In this paper, we consider the fractional edge cover packing problem, the LP relaxation of ECPP. We focus on the more general weighted setting, the weighted fractional edge cover packing problem (WFECPP), which can be formulated as the following linear program Maximize\1^ T x\subject to & A x ≤ w\& x ≥ 0, Maximize 1 T x subject to A x≤ wx≥ 0, where A is the edge–edge cover incidence matrix of G, w=(w (e): e ∈ E) w=(w (e): e∈ E), and w (e) is a positive rational weight on each edge e of G. The weighted co-density problem, closely related to WFECPP, is to find a subset S ⊆ V S⊆ V with| S| ≥ 3| S|≥ 3 and odd, such that 2w (E^+(S))| S|+ 1 2 w (E+(S))| S|+ 1 is minimized, where E^+(S) E+(S) is the set of all edges of G with at least one end in S and w (E^+(S)) w (E+(S)) is the total weight of all edges in E^+(S) E+(S). We present polynomial combinatorial algorithms for solving these two problems exactly.
登录
查看更多内容
DOI：
10.1007/bfb0070378
发表时间：
1978
期刊：
--
影响因子：
--
作者：
R. P. Gupta
通讯作者：
R. P. Gupta
影响因子：
2.7
作者：
G. Ding;Li Feng;Wenan Zang
通讯作者：
G. Ding;Li Feng;Wenan Zang
DOI：
10.1007/978-3-642-32147-4_40
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Huber A
通讯作者：
Huber A
影响因子：
2.5
作者：
GOLDBERG, AV;TARJAN, RE
通讯作者：
TARJAN, RE
DOI：
10.1137/0109047
发表时间：
1961-01-01
期刊：
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS
影响因子：
--
作者：
GOMORY, RE;HU, TC
通讯作者：
HU, TC