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

DOI10.1287/ijoc.2017.0764OpenAlexW2768502866MaRDI QIDQ5131709

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

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)

Related Items (3)

The Star Degree Centrality Problem: A Decomposition Approach ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Treewidth versus clique number. II: Tree-independence number

Uses Software

• LEMON

Cites Work

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

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