Research Article
BibTex RIS Cite

Valid Inequalities for the Maximal Matching Polytope

Year 2019, , 374 - 385, 30.12.2019
https://doi.org/10.37094/adyujsci.540858

Abstract



    Given a graph G=(V,E),






a subset M of E is called a matching
if no two edges in M
 are adjacent. A
matching is said to be maximal if it is not a proper subset of any other
matching. The maximal matching polytope associated with graph G
is the convex hull of
the incidence vectors of maximal matchings in G
. In this paper, we introduce new classes of valid
inequalities for the maximal matching polytope.




References

  • [1] Budinich, M., Exact bounds on the order of the maximum clique of a graph, Discrete Applied Mathematics, 127(3), 535-543, 2003.
  • [2] Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope, Mathematical Programming, 47(1-3), 367-387, 1990.
  • [3] Taşkın, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem, Optimization Letters, 6, 1161-1171, 2012.
  • [4] Yannakakis, M., Gavril, F., Edge dominating sets in graphs, SIAM Journal of Applied Mathematics, 38, 364-372, 1980.
  • [5] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
  • [6] Horton, J.D., Kilakos, K., Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6(3), 375-387, 1993.
  • [7] Demange, M., Ekim, T., Minimum Maximal Matching is NP-Hard in Regular Bipartite Graphs, in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4978, 364-374, Springer, Berlin, 2008.
  • [8] Mitchell, S., Hedetniemi, S.T., Edge domination in trees, in: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, 19, 489–509, 1977.
  • [9] Richey, M.B., Parker, R.G., Minimum-maximal matching in series-parallel graphs, European Journal of Operational Research, 33(1), 98–105, 1988.
  • [10] Hwang, S.F., Chang, G.J., The edge domination problem, Discussiones Mathematicae Graph Theory, 15(1), 51–57, 1995.
  • [11] Cardinal, J., Langerman, S., Levy, E., Improved approximation bounds for edge dominating set in dense graphs, Theoretical Computer Science, 410, 949–957, 2009.
  • [12] Chlebík, M., Chlebíková, J., Approximation hardness of edge dominating set problems, Journal of Combinatorial Optimization, 11(3), 279–290, 2006.
  • [13] Bodur, M., Ekim, T., Taşkın, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem, Networks, 62, 273–287, 2013.
  • [14] Tural, M.K., Maximal matching polytope in trees, Optimization Methods and Software, 31(3), 471-478, 2016.

Maksimal Eşleme Politopu için Geçerli Eşitsizlikler

Year 2019, , 374 - 385, 30.12.2019
https://doi.org/10.37094/adyujsci.540858

Abstract


    Verilen bir G=(V,E) çizgesinde, uçları
kesişmeyen kenarlardan oluşan M k
ümesine eşleme denir.
Herhangi başka bir eşlemenin öz altkümesi olmayan bir eşlemeye maksimal eşleme
denir. G çizgesindeki maksimal eşlemelerin insidans vektörlerinin konveks
örtüsüne G kümesi ile ilişkili maksimal eşleme politopu adı verilir. Bu çalışmada,
maksimal eşleme politopu için yeni geçerli eşitsizlik sınıfları sunulmaktadır.




References

  • [1] Budinich, M., Exact bounds on the order of the maximum clique of a graph, Discrete Applied Mathematics, 127(3), 535-543, 2003.
  • [2] Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope, Mathematical Programming, 47(1-3), 367-387, 1990.
  • [3] Taşkın, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem, Optimization Letters, 6, 1161-1171, 2012.
  • [4] Yannakakis, M., Gavril, F., Edge dominating sets in graphs, SIAM Journal of Applied Mathematics, 38, 364-372, 1980.
  • [5] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
  • [6] Horton, J.D., Kilakos, K., Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6(3), 375-387, 1993.
  • [7] Demange, M., Ekim, T., Minimum Maximal Matching is NP-Hard in Regular Bipartite Graphs, in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4978, 364-374, Springer, Berlin, 2008.
  • [8] Mitchell, S., Hedetniemi, S.T., Edge domination in trees, in: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, 19, 489–509, 1977.
  • [9] Richey, M.B., Parker, R.G., Minimum-maximal matching in series-parallel graphs, European Journal of Operational Research, 33(1), 98–105, 1988.
  • [10] Hwang, S.F., Chang, G.J., The edge domination problem, Discussiones Mathematicae Graph Theory, 15(1), 51–57, 1995.
  • [11] Cardinal, J., Langerman, S., Levy, E., Improved approximation bounds for edge dominating set in dense graphs, Theoretical Computer Science, 410, 949–957, 2009.
  • [12] Chlebík, M., Chlebíková, J., Approximation hardness of edge dominating set problems, Journal of Combinatorial Optimization, 11(3), 279–290, 2006.
  • [13] Bodur, M., Ekim, T., Taşkın, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem, Networks, 62, 273–287, 2013.
  • [14] Tural, M.K., Maximal matching polytope in trees, Optimization Methods and Software, 31(3), 471-478, 2016.
There are 14 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Mathematics
Authors

Mustafa Kemal Tural 0000-0002-7173-7646

Publication Date December 30, 2019
Submission Date March 16, 2019
Acceptance Date December 18, 2019
Published in Issue Year 2019

Cite

APA Tural, M. K. (2019). Valid Inequalities for the Maximal Matching Polytope. Adıyaman University Journal of Science, 9(2), 374-385. https://doi.org/10.37094/adyujsci.540858
AMA Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. December 2019;9(2):374-385. doi:10.37094/adyujsci.540858
Chicago Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science 9, no. 2 (December 2019): 374-85. https://doi.org/10.37094/adyujsci.540858.
EndNote Tural MK (December 1, 2019) Valid Inequalities for the Maximal Matching Polytope. Adıyaman University Journal of Science 9 2 374–385.
IEEE M. K. Tural, “Valid Inequalities for the Maximal Matching Polytope”, ADYU J SCI, vol. 9, no. 2, pp. 374–385, 2019, doi: 10.37094/adyujsci.540858.
ISNAD Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science 9/2 (December 2019), 374-385. https://doi.org/10.37094/adyujsci.540858.
JAMA Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. 2019;9:374–385.
MLA Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science, vol. 9, no. 2, 2019, pp. 374-85, doi:10.37094/adyujsci.540858.
Vancouver Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. 2019;9(2):374-85.

...