Co-density and fractional edge cover packing

Qiulan Zhao (), Zhibin Chen and Jiajun Sang
Additional contact information
Qiulan Zhao: Nanjing University
Zhibin Chen: Kunming University of Science and Technology
Jiajun Sang: The University of Hong Kong

Journal of Combinatorial Optimization, 2020, vol. 39, issue 4, No 2, 955-987

Abstract: Abstract 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 $$\begin{aligned} \begin{array}{ll} \hbox {Maximize} \ \ \ &{} {{\varvec{1}}}^T {{\varvec{x}}} \\ \hbox {subject to} &{} A{{\varvec{x}}} \le {{\varvec{w}}} \\ &{} \quad {{\varvec{x}}} \ge {{\varvec{0}}}, \end{array} \end{aligned}$$Maximize1Txsubject toAx≤wx≥0,where A is the edge–edge cover incidence matrix of G, $${\varvec{w}}=(w(e): e\in 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\subseteq V$$S⊆V with $$|S|\ge 3$$|S|≥3 and odd, such that $$\frac{2w(E^{+}(S))}{|S|+1}$$2w(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.

Keywords: Multigraph; Fractional packing; Edge cover; Co-density; Combinatorial algorithm; Primary 90C27; 68Q25 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00535-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00535-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00535-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().