On combinatorial optimization for dominating sets (literature survey, new models)
The paper focuses on some versions of connected dominating set problems: basic problems and multicriteria problems. A literature survey on basic problem formulations and solving approaches is presented. The basic connected dominating set problems are illustrated by simplifyed numerical examples. New integer programming formulations of dominating set problems (with multiset estimates) are suggested.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSurveySimilar Papers 제목 키워드 기반
Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks
A dominating set of a graph $\mathcal{G=(V, E)}$ is a subset of vertices $S\subseteq\mathcal{V}$ such that every vertex $v\in \mathcal{V} \setminus S$ outside the dominating set is adjacent to a vertex $u\in S$ within th…
Combinatorial OptimizationA Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem
Minimum connected dominating set problem is an NP-hard combinatorial optimization problem in graph theory. Finding connected dominating set is of high interest in various domains such as wireless sensor networks, optical…
Combinatorial OptimizationMultiobjective OptimizationCombinatorial Landscape Analysis for Dominating Set and Vertex Coloring
We analyze the two combinatorial problems of Dominating Set and Vertex Coloring regarding what kind of local optima are present for various instances. For a variety of graph classes each, we determine whether the induced…
Visual Affordance and Function Understanding: A Survey
Nowadays, robots are dominating the manufacturing, entertainment and healthcare industries. Robot vision aims to equip robots with the ability to discover information, understand it and interact with the environment. The…
Affordance DetectionScene UnderstandingSurveyMessage Passing and Combinatorial Optimization
Graphical models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying o…
ClusteringCombinatorial OptimizationTraveling Salesman Problem