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