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 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 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 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]

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]

Abstract: Labelle and Lamathe introduced in 2009 a generalization of the standard combinatorial differential species operator D, by giving a combinatorial interpretation to , where and are two-sort and one-sort species respectively. One can show that such operators can be decomposed as sums of products of simpler operators called atomic combinatorial differential operators. In their paper, Labelle and Lamathe presented a list of the first atomic differential operators. In this paper, we describe an algorithm that allows to generate (and enumerate) all of them, subject to available computer resources. We also give a detailed analysis of how to compute the molecular components of . [Copyright &y& Elsevier]

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 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]

This paper discusses a mathematical concept of language that models both artificial and natural languages and thus provides a framework for a unified language processing methodology. This concept of a language is regarded as a communication tool that allows language users to develop knowledges, while interacting with their universe of discourse, and to communicate with each other, while exchanging knowledges. Criteria for consistent usage of a language are established using a Galois connection between language syntax and language semantics. Solutions to ambiguity, paraphrase, attitude, and other problems concerning the relationship between syntax and semantics are addressed. A general schema for language specification is introduced and algorithms that perform language generation and language analysis are discussed as universal tools defined by the specification schema. Language transformations performed by various kinds of translators are examined and correctness criteria of these translators are defined using the language Galois connection.The paper is structured as follows: Section 1 introduces the framework and justifies the necessity of a unified methodology for language processing. Section 2 presents the mathematical concept of a language. Section 3 illustrates the mathematical concept of a language with three kinds of language structures: natural language, logical language, and programming language. Section 4 discusses the algebraic mechanism of language specification that unifies the methodology for language processing tool development. Section 5 formalizes the criterion for the consistency of the language usage, defines the architecture of a unified language processing system, and shows how the consistency criteria for language usage can be employed as correctness criteria for the algorithms performing various language transformations. [Copyright &y& Elsevier]

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]

Abstract: In this paper we introduce the V-transform (V-BWT), a variant of the classic Burrows–Wheeler Transform. The original BWT uses lexicographic order, whereas we apply a distinct total ordering of strings called V-order. V-order string comparison and Lyndon-like factorization of a string into V-words have recently been shown to be linear in their use of time and space (Daykin et al., 2011) [18]. Here we apply these subcomputations, along with suffix-sorting (Ko and Aluru, 2003) [26], to implement linear V-sorting of all the rotations of a string. When it is known that the input string x is a V-word, we compute the V-transform in time and space, and also outline an efficient algorithm for inverting the V-transform and recovering x . We further outline a bijective algorithm in the case that x is arbitrary. We propose future research into other variants of transforms using lex-extension orderings (Daykin et al., 2013) [19]. Motivation for this work arises in possible applications to data compression. [Copyright &y& Elsevier]

Abstract: A mixed dominating set of a simple graph is a subset such that every vertex or edge not in is adjacent or incident to at least one vertex or edge in . The mixed domination problem is to determine a minimum mixed dominating set of . This paper studies mixed domination in graphs from an algorithmic point of view. In particular, a linear-time labeling algorithm for the mixed domination problem in cacti is presented. In addition, we fix an incomplete proof of the NP-completeness of the mixed domination problem in split graphs Zhao et al. (2011) [23]. Finally, we establish a primal–dual algorithm for the mixed domination problem in trees. [Copyright &y& Elsevier]

Abstract: This paper presents a simple algorithm to generate all ordered trees with exactly vertices including exactly leaves. The best known algorithm generates such trees in time per tree, whereas our algorithm generates such trees in time per tree in the worst case. [Copyright &y& Elsevier]

Abstract: Given a universe containing elements and a collection of multisets or sets over , the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in time and polynomial space, where is the maximum coverage requirement and denotes the total number of given multisets over . (The notation suppresses a factor polynomial in .) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusion–exclusion principle, we can exactly solve the SMC without multiplicity constraints problem in time. Compared with two recent results, in [Q.-S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multi-covering via inclusion–exclusion, Theoretical Computer Science, 410 (38–40) (2009) 3882–3892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in time and space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general transformation for constructing self-stabilizing algorithms which utilize distance- knowledge. Our transformation has both a slowdown and space overhead in , and might be thought of as a distance- resource allocation algorithm. Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. These results can be generalized to efficiently find maximal -sets, for properties which we call local monotonic. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information. [Copyright &y& Elsevier]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]

Abstract: A semiretract of a free monoid is an intersection of a family of retracts of and it is a free submonoid. In the paper we propose an algorithmic approach to the problem of finding the base (code) of a semiretract. [Copyright &y& Elsevier]

Abstract: The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number of a graph G is the minimum cardinality of a power dominating set of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for solving the power domination problem in block graphs. As an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs. [Copyright &y& Elsevier]

Abstract: Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer , it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15–29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61–72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977–979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147–157] and it has been open for a long time whether this problem can be solved in time. In this paper, we will provide a simple and efficient -time algorithm for solving this problem. [Copyright &y& Elsevier]

Abstract: Many RNA structures are assembled from a collection of RNA motifs, which appear repeatedly and in various combinations. Identification of RNA structural motifs will enhance our understanding of RNA structures and functions. Searching for secondary structural patterns in sequence databases is the basic technique and fundamental problem for extracting and identifying such motifs. A number of algorithms and programs have been developed for this purpose. In this paper, we adopt a representation of secondary structure called secondary expressions, and present two algorithms for finding all exact matches of a given secondary expression. [Copyright &y& Elsevier]

Abstract: A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class , is called the overhead of algorithm for the class of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or—in one case—close to smallest, overhead. While for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at least but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is . We also consider exploration of the class of lines (simple paths). In this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is . Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is . An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms. [Copyright &y& Elsevier]

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]