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
Valid Inequalities for the Maximal Matching Polytope
Date
2019-12-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
155
views
0
downloads
Cite This
Given a graph G=(V,E), a subset M of E is called a matching if no two edges in M are adjacent. A matching is said to be maximal if it is not a proper subset of any other matching. The maximal matching polytope associated with graph G is the convex hull of the incidence vectors of maximal matchings in G. In this paper, we introduce new classes of valid inequalities for the maximal matching polytope.
Subject Keywords
Matching
,
Maximal matching polytope
,
Matching polytope
,
Valid inequalities
,
Maximal matching
,
Eşleme
,
Maksimal eşleme politopu
,
Eşleme politopu
,
Geçerli eşitsizlikler
,
Maksimal Eşleme
URI
https://hdl.handle.net/11511/57995
Journal
Adıyaman University Journal of Science
DOI
https://doi.org/10.37094/adyujsci.540858
Collections
Department of Industrial Engineering, Article
Suggestions
OpenMETU
Core
Integer Programming and Heuristic Approaches for the Dominating Tree Problem
Akifoğlu, Selin; Tural, Mustafa Kemal (null; 2016-07-03)
Let G=(V, E) be a simple undirected edge-weighted graph, where V and E denote the set of vertices and edges of G, respectively. The Dominating Tree Problem (DTP) searches for a minimum weighted tree in G, say DT, such that each vertex either belongs to DT or is one-hop away from DT. This problem is an NP-hard but a practical problem. The solution of the DTP is used to construct a backbone for wireless sensor networks, which have a wide usage in many industrial and consumer applications. In this paper, diffe...
Integer programming approaches to the dominating Tree problem
Akifoğlu, Selin; Tural, Mustafa Kemal; Department of Industrial Engineering (2016)
Let G=(V,E) be a simple undirected edge-weighted graph, where V and E denote the set of vertices and edges of G, respectively. The Dominating Tree Problem (DTP) searches for a minimum weighted tree in G, say DT, such that each vertex either belongs to DT or is one-hop away from DT. This problem is an NP-hard but a practical problem. The solution of the DTP is used to construct a backbone for wireless sensor networks, which have a wide usage in many industrial and consumer applications. In this thesis, diffe...
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.
Coarse-to-Fine Isometric Shape Correspondence by Tracking Symmetric Flips
Sahillioğlu, Yusuf; Yemez, Y. (2013-02-01)
We address the symmetric flip problem that is inherent to multi-resolution isometric shape matching algorithms. To this effect, we extend our previous work which handles the dense isometric correspondence problem in the original 3D Euclidean space via coarse-to-fine combinatorial matching. The key idea is based on keeping track of all optimal solutions, which may be more than one due to symmetry especially at coarse levels, throughout denser levels of the shape matching process. We compare the resulting den...
Invariant subspaces for Banach space operators with an annular spectral set
Yavuz, Onur (2008-01-01)
Consider an annulus Omega = {z epsilon C : r(0) 0 such that parallel to p(T)parallel to <= K sup{vertical bar p(lambda)vertical bar : vertical bar lambda vertical bar <= 1} and parallel to p(r(0)T(-1))parallel to <= K sup{vertical bar p(lambda)vertical bar : vertical bar lambda vertical bar <= 1} for all polynomials p. Then there exists a nontrivial common invariant subspace for T* and T*(-1).
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. K. Tural, “Valid Inequalities for the Maximal Matching Polytope,”
Adıyaman University Journal of Science
, pp. 374–385, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57995.