Minimum Weighted Maximal Matching Problem in Trees

Date

2015-06-21

Author

Tural, Mustafa Kemal

Metadata

Show full item record

Item Usage Stats

132
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. We show that the convex hull of the incidence vectors of maximal matchings (i.e., the maximal matching polytope) in trees is given by the polyhedron 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 in open.

URI

http://s3-eu-west-1.amazonaws.com/kg15/production/news/5_book_of_abstracts.pdf?1434179614
https://hdl.handle.net/11511/73200

Conference Name

8th Slovenian Conference on Graph Theory, (21-27 Haziran 2015)

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Maximal matching polytope in trees Tural, Mustafa Kemal (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)...
Minimum variance quadratic unbiased estimation for the variance components in simple linear regression with onefold nested error Gueven, Ilgehan (Informa UK Limited, 2006-01-01) The explicit forms of the minimum variance quadratic unbiased estimators (MIVQUEs) of the variance components are given for simple linear regression with onefold nested error. The resulting estimators are more efficient as the ratio of the initial variance components estimates increases and are asymptotically efficient as the ratio tends to infinity.
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
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 TIGHTER BAYESIAN CRAMER-RAO BOUND Bacharach, Lucien; Fritsche, Carsten; Orguner, Umut; Chaumette, Eric (2019-01-01) It has been shown lately that any "standard" Bayesian lower bound (BLB) on the mean squared error (MSE) of the Weiss-Weinstein family (WWF) admits a "tighter" form which upper bounds the "standard" form. Applied to the Bayesian Cramer-Rao bound (BCRB), this result suggests to redefine the concept of efficient estimator relatively to the tighter form of the BCRB, an update supported by a noteworthy example. This paper lays the foundation to revisit some Bayesian estimation problems where the BCRB is not tigh...

Citation Formats

M. K. Tural, “Minimum Weighted Maximal Matching Problem in Trees,” presented at the 8th Slovenian Conference on Graph Theory, (21-27 Haziran 2015), Kranjska Gora, Slovenya, 2015, Accessed: 00, 2021. [Online]. Available: http://s3-eu-west-1.amazonaws.com/kg15/production/news/5_book_of_abstracts.pdf?1434179614.