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]

In this paper we consider the problem of maximizing a non-monotone and non-negative DR-submodular function on a bounded integer lattice [ B → ] = { (x 1 , ... , x n) ∈ Z + n : 0 ≤ x k ≤ B k , ∀ 1 ≤ k ≤ n } without any constraint, where B → = (B 1 , ... , B n) ∈ Z + n. We design an algorithm for the problem and measure its performance by its approximation ratio and the number of value oracle queries it needs, where the latter one is the dominating term in the running time of an algorithm. It has been showed that, for the problem considered, any algorithm achieving an approximation ratio greater than 1 2 requires an exponential number of value oracle queries. In the literature there are two algorithms that reach 1 2 approximation guarantee. The first algorithm needs O (n | | B | | ∞) oracle queries. The second one reduces its number of oracle queries to O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) but it needs large storage. In this paper we present a randomized approximation algorithm that has an approximation guarantee of 1 2 , calls O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) oracle queries and does not need large storage, improving the results of the literature. [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 shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T = (W ⊎ B , E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et al. [6] that the total length of all shortest augmenting paths found is O (n log ⁡ n). In this paper we prove a tight O (n log ⁡ n) upper bound for the total length of shortest augmenting paths for trees improving over O (n log 2 ⁡ n) bound [3]. [ABSTRACT FROM AUTHOR]

• In this paper, we provide a formal definition of a causal broadcast abstraction in the presence of Byzantine processes. • We present a simple causal broadcast algorithm that implements this specification in the presence of Byzantine processes. • We prove our algorithm to be correct under the specification we have provided. • One difficulty consists in proving that an adversary cannot destroy the causality between broadcasts of correct processes. • We illustrate how our algorithm can help implement a money transfer object, with potential application to cryptocurrencies. Causal broadcast is a communication abstraction built on top of point-to-point send/receive networks that ensures that any two messages whose broadcasts are causally related (as captured by Lamport's "happened before" relation) are delivered in their sending order. Several causal broadcast algorithms have been designed for failure-free and crash-prone asynchronous message-passing systems. This article first gives a formal definition of a causal broadcast abstraction in the presence of Byzantine processes, in the form of two equivalent characterizations, and then presents a simple causal broadcast algorithm that implements it. The main difficulty in the design and the proof of this algorithm comes from the very nature of Byzantine faults: Byzantine processes may have arbitrary behavior, and the algorithm must ensure that correct processes (i) maintain a coherent view of causality and (ii) are never prevented from communicating between themselves. To this end, the algorithm is built modularly, namely it works on top of any Byzantine-tolerant reliable broadcast algorithm. Due to this modularity, the proposed algorithm is easy to understand and inherits the computability assumptions (notably the maximal number of processes that may be Byzantine) and the message/time complexities of the underlying reliable broadcast on top of which it is built. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1.4 + ε. This is achieved through a deep investigation of the optimal solution structure of Two-Sided Scaffold Filling. We make use of a relevant graph aiming at a solution of a Two-Sided Scaffold Filling instance, and evaluate the optimal solution value by the number of connected components in this graph. We show that an arbitrary optimal solution can be transformed into one whose relevant graph admits connected components that are available to compare with the solution of our algorithm in terms of their values. The performance ratio 1.4 + ε is obtained by comparing the bound of such an optimal solution with the solution of our algorithm. [ABSTRACT FROM AUTHOR]

A rectangular floorplan (RFP) is a partition of a rectangle R into rectangles R 1 , R 2 , ... , R n such that no four of them meet at a point. Rectangular floorplans find their applications in VLSI circuits floorplanning and architectural floorplanning. Let G represent the graph of a rectangular floorplan RFP 1 (n) and H be a subgraph of G , where n denotes the number of rectangles in RFP 1 (n). It is well known that every subgraph of G may not admit an RFP, i.e., G does not have a hereditary property. Hence, in this paper, we first derive a necessary and sufficient condition for H to admit a rectangular floorplan RFP 2 (n). Further, if H admits an RFP, we present a linear time transformation algorithm for deriving RFP 2 (n) from RFP 1 (n). • Existence of a rectangular floorplan for a subgraph of the graph representing a rectangular floorplan is shown. • A transformation algorithm has been proposed to transform a rectangular floorplan to another rectangular floorplan. • Application to VLSI circuits design and architectural design have been discussed. [ABSTRACT FROM AUTHOR]

The Minimum Vertex Cover P roblem is the optimization problem of finding a vertex cover V c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this paper, we start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We study the new algorithm theoretically and empirically, and run simulations to compare its performance to that of some algorithms of a similar nature. [ABSTRACT FROM AUTHOR]

The concept of the locating-chromatic number for graphs was introduced by Chartrand et al. (2002). In this paper, we propose an algorithm to determine the upper bound of the locating-chromatic number of any tree. This algorithm works much better than the one given by Furuya and Matsumoto (2019). [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]

The locating-chromatic number of a graph G (V , E) is the cardinality of a minimum resolving partition of the vertex set V (G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices not contained in the same partition class. Determining the locating-chromatic number of any tree is a difficult task. In this paper, we propose an algorithm to compute the upper bound on the locating-chromatic number of any tree. To do so, we decompose a tree into caterpillars and then compute the upper bound of the locating-chromatic number of this tree in terms of the ones for these caterpillars. [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]

Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. introduced popular branchings. Let G = (V G , E G) be a directed graph, where each vertex has preferences over its incoming arcs, and B and B ′ be branchings in G. A vertex v ∈ V G prefers B to B ′ if v prefers its incoming arc of B to that of B ′ , where having an arbitrary incoming arc is preferred to having no incoming arc. We say that B is more popular than B ′ if the number of vertices preferring B to B ′ is greater than the number of vertices preferring B to B ′. A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The correctness of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs, in the same manner as weighted popular matchings by Mestre. We give an algorithm for finding a weighted popular branching for the case where the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm is based on Kavitha et al.'s algorithm, while it includes elaborated procedures resulting from the vertex-weights. Its correctness also builds upon the duality of weighted arborescences. [ABSTRACT FROM AUTHOR]

In this paper, we consider rainbow connection number of maximal outerplanar graphs (MOPs) on algorithmic aspect. For the (MOP) G , we give sufficient conditions to guarantee that r c ( G ) = d i a m ( G ) . Moreover, we produce the graph with given diameter D and give their rainbow coloring in linear time. X. Deng et al. [4] give a polynomial time algorithm to compute the rainbow connection number of MOPs by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri [11] proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut-spine of MOP G , by which we design an algorithm to give a rainbow edge coloring with at most 2 r a d ( G ) + 2 + c , 0 ≤ c ≤ r a d ( G ) − 2 colors in polynomial time. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of partitioning a convex polygon P of n vertices into m polygons of equal area and perimeter. We give an algorithm for m = 2 that runs in O ( n ) time, and an algorithm for m = 2 k , where k is an integer, that runs in O ( ( 2 n ) k ) time. These are the first algorithms to solve this problem. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) with a positive weight function w on the vertices of G , a global powerful alliance of G is a subset S of V such that for every vertex v at least half of the total weight in the closed neighborhood of v is contributed by the vertices of S . A global offensive alliance is a subset S of V such that the above condition holds for every vertex v not in S . Finding the smallest such set in general graphs is NP-complete for both of these problems, even when the weights are all the same. In this paper, we give linear time algorithms that find the smallest global offensive and global powerful alliance of any weighted tree T = ( V , E ) . [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]

This paper presents a practical decision procedure for Propositional Projection Temporal Logic with infinite models. First, a set Prop l of labels l i , 0 ⩽ i ⩽ n ∈ N 0 , is used to mark nodes of an LNFG of a formula, and a node with l i is treated as an accepting state as in an automaton. Further, the generalized Büchi accepting condition for automata is employed to identify a path (resulting a word) in an LNFG as a model of the formula. In addition, the implementation details of the decision procedure and relevant algorithms including pre-processing, LNFG, circle finding algorithms are presented; as a matter of fact, all algorithms are implemented by C++ programs. [ABSTRACT FROM AUTHOR]