Maximal matching polytope in trees

Date

2016-06-01

Author

Tural, Mustafa Kemal

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

166
views

0
downloads

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.

Subject Keywords

Graph theory, Matching, Integer programming, Linear programming, Polyhedral combinatorics, 90C05, 90C10, 90C57, 05C05, 05C70

URI

https://hdl.handle.net/11511/34550

Journal

OPTIMIZATION METHODS & SOFTWARE

DOI

https://doi.org/10.1080/10556788.2015.1104679

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Minimum Weighted Maximal Matching Problem in Trees Tural, Mustafa Kemal (2015-06-21) Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. We show that the convex hull of the incidence vectors of maximal matchings (i.e., the maximal matching polytope) in trees...
Minimum weighted perfect neighborhood set problem Hastürk, Umur; Tural, Mustafa Kemal; Department of Operational Research (2020) Given an undirected simple graph G = (V,E), the open neighborhood of a vertex j ∈ V , denoted by δ(j), is defined as the set of all vertices that are adjacent to j , i.e., δ(j) = {i
On maximal curves and linearized permutation polynomials over finite fields Özbudak, Ferruh (Elsevier BV, 2001-08-08) The purpose of this paper is to construct maximal curves over large finite fields using linearized permutation polynomials. We also study linearized permutation polynomials under finite field extensions.
Efficient basket Monte Carlo option pricing via a simple analytical approximation Korn, Ralf; Zeytun, Serkan (2013-05-01) We present a new valuation method for basket options that is based on a limiting approximation of the arithmetic mean by the geometric mean. Using this approximation combined with a new analytical pricing formula for an approximating geometric mean-based option as a control variate, excellent performance for Monte Carlo pricing in a control variate setting is obtained.
A minisum location problem with regional demand considering farthest Euclidean distances DİNLER, DERYA; Tural, Mustafa Kemal (2016-06-01) We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to ...

Citation Formats

M. K. Tural, “Maximal matching polytope in trees,” OPTIMIZATION METHODS & SOFTWARE, pp. 471–478, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/34550.