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 perfect neighborhood set problem
Download
index.pdf
Date
2020
Author
Hastürk, Umur
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
137
views
57
downloads
Cite This
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
Subject Keywords
Integer programming.
,
Perfect Neighborhood Set
,
Integer Programming
,
Valid Inequality
,
Tree
,
Dominating Set.
URI
http://etd.lib.metu.edu.tr/upload/12625520/index.pdf
https://hdl.handle.net/11511/45742
Collections
Graduate School of Natural and Applied Sciences, Thesis
Suggestions
OpenMETU
Core
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...
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...
A strong conic quadratic reformulation for machine-job assignment with controllable processing times
Akturk, M. Selim; Atamturk, Alper; Gürel, Sinan (2009-05-01)
we describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation.
Inequalities for harmonic functions on spheroids and their applications
Zahariuta, V (2001-06-01)
Hadamard-type interpolational inequalities for norms of harmonic functions are studied for confocal prolate and oblate spheroids. It is shown that the optimal level domains in such inequalities may be non-spheroidal. Moreover, in contrary with the case of analytic functions, there is an unremovable gap between the corresponding optimal level domains for inner and outer versions of Hadamard-type inequalities for harmonic functions. These results are based on some special asymptotical formulas for associated ...
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)...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
U. Hastürk, “Minimum weighted perfect neighborhood set problem,” Thesis (M.S.) -- Graduate School of Informatics. Operational Research., Middle East Technical University, 2020.