integer linear programming

Today, the desire to use mixed-critical systems in the industry is increasing. In order to provide the processing power required by mixed-critical systems, multi-core architectures are considered a suitable option. One of the main challenges in mixed-critical systems is task scheduling, which is even more challenging in multi-core architectures. Many studies of task scheduling in mixed-critical multi-core systems have dealt with the scheduling of independent tasks. But in many real systems, tasks are dependent on each other. In this research, we will deal with the scheduling of dependent periodic tasks in mixed-critical multi-core systems in such a way that the presented schedule satisfies the system constraints. The proposed algorithm provides the best possible schedule using linear programming. The results of the experiments showed that the presented method has been able to significantly reduce the number of preemptions while maintaining the scheduling capability.

For a simple, undirected graph $G(V,E)$, a function $h : V(G) rightarrow lbrace 0, 1, 2rbrace$ such that each edge $ (u,v)$ of $G$ is either incident with a vertex with weight at least one or there exists a vertex $w$ such that either $(u,w) in E(G)$ or  $(v,w) in E(G)$ and $h(w) = 2$, is called a vertex-edge Roman dominating function (ve-RDF) of $G$. For a graph $G$, the smallest possible weight of a ve-RDF of $G$ which is denoted by $gamma_{veR}(G)$, is known as the textit{vertex-edge Roman domination number} of $G$. The problem of determining  $gamma_{veR}(G)$ of a graph $G$ is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if $G$ has a ve-RDF of weight at most $l$ for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming  formulation for MVERDP is presented.

Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman ${3}$-domination. A function $g : V(G) rightarrow lbrace 0, 1, 2, 3 rbrace$ having the property that $sum_{v in N_G(u)}^{} g(v) geq 3$, if $g(u) = 0$, and $sum_{v in N_G(u)}^{} g(v) geq 2$, if $g(u) = 1$ for any vertex $u in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an textit{ independent Roman ${3}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = sum_{v in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman ${3}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $lbrace 3 rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.