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
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
132
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. 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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.