File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/17M1147676
- Scopus: eid_2-s2.0-85061007516
- WOS: WOS:000462593800010
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Densities, Matchings, and Fractional Edge-Colorings
Title | Densities, Matchings, and Fractional Edge-Colorings |
---|---|
Authors | |
Keywords | Algorithm Density Fractional edge-coloring Matching Multigraph |
Issue Date | 2019 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at https://www.siam.org/Publications/Journals/SIAM-Journal-on-optimization-siopt |
Citation | SIAM Journal on Optimization, 2019, v. 29 n. 1, p. 240-261 How to Cite? |
Abstract | 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 |U| ≥ 3 and odd, that maximizes 2w(U)/(|U| − 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. © 2019 Society for Industrial and Applied Mathematics. |
Persistent Identifier | http://hdl.handle.net/10722/277237 |
ISSN | 2023 Impact Factor: 2.6 2023 SCImago Journal Rankings: 2.138 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, X | - |
dc.contributor.author | Zang, W | - |
dc.contributor.author | Zhao, Q | - |
dc.date.accessioned | 2019-09-20T08:47:12Z | - |
dc.date.available | 2019-09-20T08:47:12Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | SIAM Journal on Optimization, 2019, v. 29 n. 1, p. 240-261 | - |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | http://hdl.handle.net/10722/277237 | - |
dc.description.abstract | 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 |U| ≥ 3 and odd, that maximizes 2w(U)/(|U| − 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. © 2019 Society for Industrial and Applied Mathematics. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at https://www.siam.org/Publications/Journals/SIAM-Journal-on-optimization-siopt | - |
dc.relation.ispartof | SIAM Journal on Optimization | - |
dc.rights | SIAM Journal on Optimization. Copyright © Society for Industrial and Applied Mathematics. | - |
dc.rights | © [year] Society for Industrial and Applied Mathematics. First Published in [Publication] in [volume and number, or year], published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Algorithm | - |
dc.subject | Density | - |
dc.subject | Fractional edge-coloring | - |
dc.subject | Matching | - |
dc.subject | Multigraph | - |
dc.title | Densities, Matchings, and Fractional Edge-Colorings | - |
dc.type | Article | - |
dc.identifier.email | Zang, W: wzang@maths.hku.hk | - |
dc.identifier.authority | Zang, W=rp00839 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1137/17M1147676 | - |
dc.identifier.scopus | eid_2-s2.0-85061007516 | - |
dc.identifier.hkuros | 305304 | - |
dc.identifier.volume | 29 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 240 | - |
dc.identifier.epage | 261 | - |
dc.identifier.isi | WOS:000462593800010 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1052-6234 | - |