Minimum weighted perfect neighborhood set problem

Download
2020
Hastürk, Umur
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

Suggestions

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...
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)...
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.
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 generalized fixed point free automorphism of prime power order
Ercan, Gülin (2012-06-01)
Let G be a finite group and alpha be an automorphism of G of order p(n) for an odd prime p. Suppose that alpha acts fixed point freely on every alpha-invariant p'-section of G, and acts trivially or exceptionally on every elementary abelian alpha-invariant p-section of G. It is proved that G is a solvable p-nilpotent group of nilpotent length at most n + 1, and this bound is best possible.
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.