Maximal matching polytope in trees

2016-06-01
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.
OPTIMIZATION METHODS & SOFTWARE

Suggestions

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.
Prime graphs of solvable groups
Ulvi , Muhammed İkbal; Ercan, Gülin; Department of Electrical and Electronics Engineering (2020-8)
If $G$ is a finite group, its prime graph $Gamma_G$ is constructed as follows: the vertices are the primes dividing the order of $G$, two vertices $p$ and $q$ are joined by an edge if and only if $G$ contains an element of order $pq$. This thesis is mainly a survey that gives some important results on the prime graphs of solvable groups by presenting their proofs in full detail.
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.