Integer programming approaches to the dominating Tree problem

Download

index.pdf

Date

2016

Author

Akifoğlu, Selin

Metadata

Show full item record

Item Usage Stats

177
views

90
downloads

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, different integer programming formulations of the problem are introduced. For some instances in the literature, optimal solutions are provided for the first time and for some others best known heuristic solutions are shown to be optimal. Moreover, branch-and-cut approach is applied to the problem.

Subject Keywords

Graph algorithms., Computer algorithms., Integer programming., Wireless sensor networks.

URI

http://etd.lib.metu.edu.tr/upload/12620466/index.pdf
https://hdl.handle.net/11511/25902

Collections

Graduate School of Natural and Applied Sciences, Thesis

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...
Valid Inequalities for the Maximal Matching Polytope Tural, Mustafa Kemal (2019-12-01) 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.
Transformation-based metamaterials to eliminate the staircasing error in the finite difference time domain method Ozgun, Ozlem; Kuzuoğlu, Mustafa (Wiley, 2012-07-01) A coordinate transformation technique is introduced for the finite difference time domain method to alleviate the effects of errors introduced by the staircasing approximation of curved geometries that do not conform to a Cartesian grid. An anisotropic metamaterial region, which is adapted to the Cartesian grid and designed by the coordinate transformation technique, is constructed around the curved boundary of the object, and the region occupied between the curved boundary and the inner boundary of the ani...
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.
Characterizations of Riesz spaces with b-property Alpay, Safak; ERCAN, ZAFER (Springer Science and Business Media LLC, 2009-02-01) A Riesz space E is said to have b-property if each subset which is order bounded in E(similar to similar to) is order bounded in E. The relationship between b-property and completeness, being a retract and the absolute weak topology vertical bar sigma vertical bar (E(similar to), E) is studied. Perfect Riesz spaces are characterized in terms of b-property. It is shown that b-property coincides with the Levi property in Dedekind complete Frechet lattices.

Citation Formats

S. Akifoğlu, “Integer programming approaches to the dominating Tree problem,” M.S. - Master of Science, Middle East Technical University, 2016.