Decomposition algorithms for solving the minimum weight maximal matching problem
From MaRDI portal
Publication:2811314
DOI10.1002/net.21516zbMath1338.05212OpenAlexW2003391451MaRDI QIDQ2811314
Z. Caner Taşkın, Merve Bodur, Tınaz Ekim
Publication date: 10 June 2016
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.21516
mixed integer programmingBenders decompositionvertex coverGallai-Edmonds decompositionminimum maximal matching
Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (5)
Modelling and solving the perfect edge domination problem ⋮ Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Maximal matching polytope in trees ⋮ Minimum cost \(b\)-matching problems with neighborhoods
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- The integer \(L\)-shaped method for stochastic integer programs with complete recourse
- Approximating edge dominating set in dense graphs
- Benders decomposition for the uncapacitated multiple allocation hub location problem
- On two techniques of combining branching and treewidth
- Minimum-maximal matching in series-parallel graphs
- Partitioning procedures for solving mixed-variables programming problems
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- On approximability of the independent/connected edge dominating set problems
- Integer programming formulations for the minimum weighted maximal matching problem
- A survey on Benders decomposition applied to fixed-charge network design problems
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximation hardness of edge dominating set problems
- Approximability of the capacitated \(b\)-edge dominating set problem
- A Benders decomposition approach for the robust spanning tree problem with interval data
- Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Generalized Upper Bound Constraints
- Benders Decomposition for Large-Scale Uncapacitated Hub Location
- Minimum Edge Dominating Sets
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- Exact Algorithms for Edge Domination
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Edge Dominating Sets in Graphs
- The edge domination problem
- Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network
- Paths, Trees, and Flowers
This page was built for publication: Decomposition algorithms for solving the minimum weight maximal matching problem
