Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Minimum Weighted Maximal Matching Problem in Trees
Date
2015-06-21
Author
Tural, Mustafa Kemal
Metadata
Show full item record
Item Usage Stats
26
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.