Maximal matching polytope in trees

DOI10.1080/10556788.2015.1104679zbMath1342.90099OpenAlexW2227009375MaRDI QIDQ2815540

Mustafa Kemal Tural

Publication date: 29 June 2016

Published in: Optimization Methods and Software (Search for Journal in Brave)

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

zbMATH Keywords

linear programminginteger programmingmatchinggraph theorypolyhedral combinatorics

Mathematics Subject Classification ID

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

Related Items (2)

Integer linear programming formulations for double roman domination problem ⋮ Minimum cost \(b\)-matching problems with neighborhoods

Cites Work

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

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