Show simple item record

dc.contributor.authorSamer, Phillippe
dc.contributor.authorMoura, Phablo F S
dc.date.accessioned2024-08-13T05:48:51Z
dc.date.available2024-08-13T05:48:51Z
dc.date.created2024-08-09T16:40:23Z
dc.date.issued2024
dc.identifier.issn0166-218X
dc.identifier.urihttps://hdl.handle.net/11250/3145882
dc.description.abstractA connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available.en_US
dc.language.isoengen_US
dc.publisherElsevieren_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titlePolyhedral approach to weighted connected matchings in general graphsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2024 The Author(s)en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doi10.1016/j.dam.2024.07.042
dc.identifier.cristin2285501
dc.source.journalDiscrete Applied Mathematicsen_US
dc.source.pagenumber143-152en_US
dc.relation.projectNorges forskningsråd: 249994en_US
dc.identifier.citationDiscrete Applied Mathematics. 2024, 359, 143-152.en_US
dc.source.volume359en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal