|
Zusammenfassung:
|
This dissertation addresses methods for efficiently solving several important variants
of domination problems on graphs, with a particular focus on large-scale instances that frequ-
ently appear in real-world systems. Domination problems have numerous applications in the
analysis and management of complex networks, including social, telecommunication, transport,
and biological networks. The study covers four problems: minimum weight total domination,
minimum weight independent domination, k-strong Roman domination, and the canonical mi-
nimum domination problem on large graphs.
For the minimum weight total domination problem, a variable neighborhood search approach
is proposed, with carefully designed mechanisms for shaking, local search, and fitness function
evaluation. The results show that the proposed algorithm achieves optimal solutions on small
and medium instances and outperforms competing approaches on large graphs. Additionally,
an application of this problem for accelerating information spreading in social networks is
proposed.
For the minimum weight independent domination problem, two new integer linear pro-
gramming models are developed. Solving these models finds optimal solutions for all smaller
instances while demonstrating superior performance compared to competing exact approaches
on larger graphs. In addition, a greedy heuristic is proposed that outperforms competing greedy
methods on most instances.
In the case of k-strong Roman domination, a greedy heuristic based on node coverage
information is developed, along with a metaheuristic approach based on variable neighborhood
search that uses the greedy algorithm for initialization. This problem is particularly challenging
due to the exponential complexity of solution feasibility verification, leading to the introduction
of the concept of quasi-feasibility that enables efficient feasibility assessment during the search.
Experimental results show that the proposed algorithm consistently outperforms the greedy
approach and existing competing methods, especially on larger graphs. The practical value
of the algorithm is illustrated through a case study involving the optimal positioning of fire
stations and vehicles in urban municipalities to ensure the entire city is safe in the event of k
simultaneous fires.
For the minimum domination problem, a new hybrid approach called IRIS is proposed. IRIS
is designed as a general-purpose framework that bridges the gap between exact integer linear
programming solvers and heuristic search by iteratively fixing selected variables to reduce the
search space. Тhe novelty lies in its flexible subproblem construction mechanism, which can be
tailored using various selection strategies. In this study, we implement and evaluate a specific
configuration of IRIS that utilizes historical statistical data and a node-coverage-based heuristic
to intelligently identify variables for fixing. This targeted approach allows the ILP solver to find
high-quality solutions for large-scale instances that are computationally prohibitive for exact
methods. Experimental results demonstrate that IRIS achieves competitive performance com-
pared to the best existing methods, establishing it as a valid alternative for solving domination
and potentially other NP-hard problems. |