Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem

DOI10.1287/IJOC.2017.0764MaRDI QIDQ5131709zbMATH OpenOpenAlexFDO

Authors Betül Ahat, Tınaz Ekim, Z. Caner Taşkın

Publication date 9 November 2020

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d70bb7620ba9861290112158d373caa8b66b6d9d

zbMATH Keywords

integer programmingBenders decompositionstrong matchingmaximum induced matchingdistance-2 matching

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorics (05-XX)

Recommendations

• Integer programming formulations for the minimum weighted maximal matching problem
• On the approximability of the maximum induced matching problem
• Approximability results for the maximum and minimum maximal induced matching problems
• scientific article; zbMATH DE number 1953187
• On maximum induced matchings in bipartite graphs
• Integer program with bimodular matrix
• Large-scale mixed integer programming: Benders-type heuristics
• On the Induced Matching Problem
• On the induced matching problem

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
• Approximability results for the maximum and minimum maximal induced matching problems
• Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Finding a maximum induced matching in weakly chordal graphs
• Induced matchings
• Irredundancy in circular arc graphs
• Maximum induced matchings of random cubic graphs
• Moderately exponential time algorithms for the maximum induced matching problem
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• On the approximability of the maximum induced matching problem
• Paths, Trees, and Flowers
• The parameterized complexity of the induced matching problem

Cited in

(3)

• Treewidth versus clique number. II: Tree-independence number
• Exact Solution Algorithms for the Chordless Cycle Problem
• The star degree centrality problem: a decomposition approach

Describes a project that uses

Uses Software

• LEMON

This page was built for publication: Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5131709)