Search

The concept of rainbow connection number of a graph was introduced by Chartrand et al. in 2008. Inspired by this concept, other concepts on colored version of connectivity in graphs were introduced, such as the monochromatic connection number by Caro and Yuster in 2011, the proper connection number by Borozan et al. in 2012, and the conflict-free connection number by Czap et al. in 2018, as well as some other variants of connection numbers later on. Chakraborty et al. proved that to compute the rainbow connection number of a graph is NP-hard. For a long time, it has been tried to fix the computational complexity for the monochromatic connection number, the proper connection number and the conflict-free connection number of a graph. However, it has not been solved yet. Only the complexity results for the strong version, i.e., the strong proper connection number and the strong conflict-free connection number, of these connection numbers were determined to be NP-hard. In this paper, we prove that to compute each of the monochromatic connection number, the proper connection number and the conflict free connection number for a graph is NP-hard. This solves a long standing problem in this field, asked in many talks of workshops and papers. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A double Roman dominating function (DRDF) of G is a function f : V → { 0 , 1 , 2 , 3 } such that (i) each vertex v with f (v) = 0 is adjacent to either a vertex u with f (u) = 3 or two vertices u 1 and u 2 with f (u 1) = f (u 2) = 2 , and (ii) each vertex v with f (v) = 1 is adjacent to a vertex u with f (u) > 1. The double Roman domination number of G is the minimum weight of a DRDF along all DRDFs on G , where the weight of a DRDF f on G is f (V) = ∑ v ∈ V f (v). In this paper, we first propose an algorithm to compute the double Roman domination number of an interval graph G = (V , E) in O (| V | + | E |) time, answering a problem posed in Banerjee et al. (2020) [2]. Next, we show that the decision problem associated with the double Roman domination is NP-complete for split graphs. Finally, we show that the computational complexities of the Roman domination problem and the double Roman domination problem are different. [ABSTRACT FROM AUTHOR]

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p -Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p , and study its computational complexity. [ABSTRACT FROM AUTHOR]

In order to run a dataflow with as low cost as possible, it is often faced with deciding which data-sets in a data-set sequence should be stored, with the rest regenerated. The Intermediate Data-set Storage problem arises from this situation. The current best algorithm for this problem takes O ( n 4 ) time. In this paper, we present two improved algorithms for this problem, the first of which can achieve a time complexity O ( n 2 ) , the second of which O ( r n ) , where n is the number of data-sets in a dataflow, r is a numerical number which indicates how large it is for the maximum storage cost to be divided by the minimum computation cost in the dataflow. [ABSTRACT FROM AUTHOR]

In this paper we prove that the Minimum Latency Aggregation Scheduling (MLAS) problem in the Signal-to-Interference-Noise-Ratio (SINR) model is APX-hard in the uniform power model. [ABSTRACT FROM AUTHOR]

In this paper, at first we describe a digraph representing all the weak-order extensions of a partially ordered set and algorithms for generating them. Then we present a digraph representing all of the minimal weak-order extensions of a partially ordered set. This digraph also implies generation algorithms. Finally, we prove that the number of weak-order extensions of a partially ordered set is a comparability invariant, whereas the number of minimal weak-order extensions of a partially ordered set is not a comparability invariant. [Copyright &y& Elsevier]