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

407
views

140
downloads

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...
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.
First-principles investigation of phase stability inLixCoO2 Van der Ven, A.; Aydınol, Mehmet Kadri; Ceder, G.; Kresse, G.; Hafner, J. (American Physical Society (APS), 1998-8-1) In this work, the phase diagram of LixCoO2 is calculated from first principles for x ranging from 0 to 1. Our calculations indicate that there is a tendency for Li ordering at x=1/2 in agreement with experiment [J. N. Reimers and J. R. Dahn, J. Electrochem. Sec. 139, 2091 :1992)]. At low Li concentration, we find that a staged compound is stable in which the Li ions selectively segregate to every other Li plane leaving the remaining Li planes vacant. We do not find the two-phase region observed at high Li c...
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 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...

Citation Formats

U. Hastürk, “Minimum weighted perfect neighborhood set problem,” Thesis (M.S.) -- Graduate School of Informatics. Operational Research., Middle East Technical University, 2020.