Maximal matching polytope in trees

DOI10.1080/10556788.2015.1104679MaRDI QIDQ2815540zbMATH OpenOpenAlexFDO

Authors Mustafa Kemal Tural

Publication date 29 June 2016

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556788.2015.1104679

zbMATH Keywords

graph theoryinteger programminglinear programmingmatchingpolyhedral combinatorics

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Decomposition algorithms for solving the minimum weight maximal matching problem
• Integer programming formulations for the minimum weighted maximal matching problem
• A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• Minimum-maximal matching in series-parallel graphs

Cites work

• Approximation hardness of edge dominating set problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Edge Dominating Sets in Graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Improved approximation bounds for edge dominating set in dense graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• Maximum matching and a polyhedron with 0,1-vertices
• Minimum Edge Dominating Sets
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• Minimum-maximal matching in series-parallel graphs
• On total unimodularity of edge-edge adjacency matrices
• Short proofs on the matching polyhedron

Cited in

(10)

• Minimum-maximal matching in series-parallel graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• Minimum cost b-matching problems with neighborhoods
• Decomposition algorithms for solving the minimum weight maximal matching problem
• A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree
• scientific article; zbMATH DE number 5524949 (Why is no real title available?)
• Integer linear programming formulations for double Roman domination problem
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• Polyhedral approach to weighted connected matchings in general graphs
• Trees with maximum number of maximal matchings

This page was built for publication: Maximal matching polytope in trees

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