English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Dominating set problems are among the most important class of combinatorialproblems in graph optimization, from a theoretical as well as from a practicalpoint of view. In this paper, we address the recently introduced (minimum)weighted total domination problem. In this problem, we are given an undirectedgraph with a vertex weight function and an edge weight function. The goal is tofind a total dominating set D in this graph with minimal weight. A totaldominating set D is a subset of the vertices such that every vertex in thegraph, including vertices in D, is adjacent to a vertex in D. The weight ismeasured as the sum of all vertex weights of vertices in D, plus the edgeweights in the subgraph induced by D, plus for each vertex not in D the minimumweight of an edge from it to a vertex in D. In this paper, we present two newMixed-Integer Programming models for the problem, and design solutionframeworks based on them. These solution frameworks also include validinequalities, starting heuristics and primal heuristics. In addition, we alsodevelop a genetic algorithm, which is based on a greedy randomized adaptivesearch procedure version of our starting heuristic. We carry out acomputational study to assess the performance of our approaches when comparedto the previous work for the same problem. The study reveals that our exactsolution algorithms are up to 500 times faster compared to previous exactapproaches and instances with up to 125 vertices can be solved to optimalitywithin a timelimit of 1800 seconds. Moreover, the presented genetic algorithmalso works well and often finds the optimal or a near-optimal solution within ashort runtime. Additionally, we also analyze the influence ofinstance-characteristics on the performance of our algorithms.

Exact and heuristic algorithms for the weighted total domination problem