Integer Programming and Heuristic Approaches for the Dominating Tree Problem

Date

2016-07-03

Author

Akifoğlu, Selin
Tural, Mustafa Kemal

Metadata

Show full item record

Item Usage Stats

158
views

0
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 paper, different integer programming formulations of the problem are introduced and optimal solutions of some instances in the literature are provided for the first time. For larger instances, heuristic algorithms are proposed and compared with the algorithms from the literature

URI

https://hdl.handle.net/11511/85864

Conference Name

28th European Conference on Operational Research, (3 - 06 Temmuz 2016)

Collections

Department of Industrial Engineering, Conference / Seminar

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...
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.
Spatial synthesis by disjunctive constraint satisfaction Baykan, CA; Fox, MS (Cambridge University Press (CUP), 1997-09-01) The spatial synthesis problem addressed in this paper is the configuration of rectangles in 2D space, where the sides of the rectangles are parallel to an orthogonal coordinate system. Variables are the locations of the edges of the rectangles and their orientations. Algebraic constraints on these variables define a layout and constitute a constraint satisfaction problem. We give a new O(n(2)) algorithm for incremental path-consistency, which is applied after adding each algebraic constraint. Problem requir...
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.
WEIGHTED HOMOGENEOUS SINGULARITIES AND RATIONAL HOMOLOGY DISK SMOOTHINGS Bhupal, Mohan Lal (2011-10-01) We classify the resolution graphs of weighted homogeneous surface singularities which admit rational homology disk smoothings. The nonexistence of rational homology disk smoothings is shown by symplectic geometric methods, while the existence is verified via smoothings of negative weight.

Citation Formats

S. Akifoğlu and M. K. Tural, “Integer Programming and Heuristic Approaches for the Dominating Tree Problem,” presented at the 28th European Conference on Operational Research, (3 - 06 Temmuz 2016), Poznan, Polonya, 2016, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/85864.