Search

Abstract: For positive integers , an -labeling of a digraph D is a function f from into the set of nonnegative integers such that if x is adjacent to y in D and if x is of distance two to y in D. Elements of the image of f are called labels. The -labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an -labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. [Copyright &y& Elsevier]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V ⟶ { 0 , 1 , 2 , 3 } such that every vertex v ∈ V with f (v) = 0 is either adjacent to a vertex u with f (u) = 3 or two distinct vertices x and y with f (x) = f (y) = 2 , and every vertex v ∈ V with f (v) = 1 is adjacent to a vertex u with f (u) ≥ 2. The weight of f is the sum f (V) = ∑ v ∈ V f (v). The minimum weight of a DRDF on G is the double Roman domination number of G , denoted by γ d R (G). A graph G is a double Roman Graph if γ d R (G) = 3 γ (G) , where γ (G) is the domination number of G. In this paper, we first show that the decision problem associated to double Roman domination is NP-complete even when restricted to planar graphs. Then, we study the complexity issue of a problem posed in [R.A. Beeler, T.W. Haynesa and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29], and show that the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. Then, we give linear algorithms that compute the domination number and the double Roman domination number of a given unicyclic graph. Finally, we give a linear algorithm that decides whether a given unicyclic graph is double Roman. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array. [ABSTRACT FROM AUTHOR]

Abstract An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e (G). It follows that 1 ≤ dim e (G) ≤ n − 1 for any n -vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O (n 3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) of order n and maximum degree Δ , the NP -complete S - labeling problem consists in finding a labeling of G , i.e. a bijective mapping ϕ : V → { 1 , 2 … n } , such that SL ϕ ( G ) = ∑ u v ∈ E min { ϕ ( u ) , ϕ ( v ) } is minimized. In this paper, we study the S - labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SL ϕ ( G ) , together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SL ϕ ( G ) ≤ | E | + k is solvable in O ∗ ( 2 2 k ( 2 k ) ! ) time, thus fixed-parameterized tractable in k . We finally show that the S - Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs. [Copyright &y& Elsevier]

Abstract: This paper introduces the non-idling machine constraint where no intermediate idle time between the operations processed by a machine is allowed. In its first part, the paper considers the non-idling single-machine scheduling problem. Complexity aspects are first discussed. The “Earliest Non-Idling” property is then introduced as a sufficient condition so that an algorithm solving the original problem also solves its non-idling variant. Moreover it is shown that preemptive problems do have that property. The critical times of an instance are then introduced and it is shown that when their number is polynomial, as for equal-length jobs, a polynomial algorithm solving the original problem has a polynomial variant solving its non-idling version. [Copyright &y& Elsevier]

Abstract: The path-partition problem is to find a minimum number of vertex-disjoint paths that cover all vertices of a given graph. This paper studies the path-partition problem from an algorithmic point of view. As the Hamiltonian path problem is NP-complete for many classes of graphs, so is the path-partition problem. The main result of this paper is to present a linear-time algorithm for the path-partition problem in graphs whose blocks are complete graphs, cycles or complete bipartite graphs. [Copyright &y& Elsevier]

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]

In this paper, we investigate the reconstruction of permutations on { 1 , 2 , … , n } from betweenness constraints involving the minimum and the maximum element located between t and t + 1 , for all t = 1 , 2 , … , n − 1 . We propose two variants of the problem (directed and undirected), and focus first on the directed version, for which we draw up general features and design a polynomial algorithm in a particular case. Then, we investigate necessary and sufficient conditions for the uniqueness of the reconstruction in both directed and undirected versions, using a parameter k whose variation controls the stringency of the betweenness constraints. We finally point out open problems. [ABSTRACT FROM AUTHOR]

Abstract: For a fixed positive integer , a -tuple total dominating set of a graph is a set such that every vertex of is adjacent to at least vertices in . The -tuple total domination problem is to determine a minimum -tuple total dominating set of . This paper studies -tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the -tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the -tuple total domination problem in undirected path graphs. [Copyright &y& Elsevier]

Abstract: We consider a frequency allocation problem, in which we are given a cellular telephone network whose geographical coverage area is divided into cells in which phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e., to minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we present a 1-local 4/3-competitive distributed algorithm for multicoloring a hexagonal graph without certain forbidden configuration (introduced in Šparl and Žerovnik (2010) [7]). [Copyright &y& Elsevier]

Abstract: For a positive integer , a -dominating set of a graph is a subset such that every vertex not in is adjacent to at least vertices in . The -domination problem is to determine a minimum -dominating set of . This paper studies the -domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the -domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the -domination problem in split graphs. [Copyright &y& Elsevier]

Abstract: Given a positive integer and an undirected edge-weighted connected simple graph with at least edges of positive weight, we wish to partition the graph into edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible. [Copyright &y& Elsevier]

Abstract: A set of vertices in a graph with no isolated vertices is a paired-dominating set of if every vertex of is adjacent to at least one vertex in and if the subgraph induced by contains a perfect matching. Let be a permutation graph and be its corresponding permutation. In this paper we present an time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph with vertices and edges. [Copyright &y& Elsevier]

Abstract: In this paper we develop approximation algorithms for generalizations of the following three known combinatorial optimization problems, the Prize-Collecting Steiner Tree problem, the Prize-Collecting Travelling Salesman Problem and a Location-Routing problem. Given a graph on vertices and a length function on its edges, in the grouped versions of the above mentioned problems we assume that is partitioned into groups, , with a penalty function on the groups. In the Group Prize-Collecting Steiner Tree problem the aim is to find , a collection of groups of and a tree spanning the rest of the groups not in , so as to minimize the sum of the costs of the edges in the tree and the costs of the groups in . The Group Prize-Collecting Travelling Salesman Problem, is defined analogously. In the Group Location-Routing problem the customer vertices are partitioned into groups and one has to select simultaneously a subset of depots to be opened and a collection of tours that covers the customer groups. The goal is to minimize the costs of the tours plus the fixed costs of the opened depots. We give a -approximation algorithm for each of the three problems, where is the cardinality of the largest group. [Copyright &y& Elsevier]

Abstract: The general all-ones problem is defined as follows: Given a graph , where V and E denote the vertex-set and the edge-set of G, respectively. Denote C as an initial subset of V. The problem is to find a subset X of V such that for every vertex of the number of vertices in X adjacent to is odd while for every vertex of C the number is even. X is called a solution to the problem. When , this problem is the so-called all-ones problem. If a vertex is viewed to be adjacent to itself, the all-ones problem is addressed as the all-ones problem. The all-ones problem has been studied extensively. However, the all-ones problem has received much less attention. Unlike the all-ones problem, which has solutions for any graphs, the all-ones problem may not have solutions for many graphs, even for some very simple graphs like and . So, it becomes an interesting question to find polynomial time algorithms to determine if for a given tree the problem has solutions. And if it does, to find a solution to the minimum all-ones problem. In this paper we present two algorithms of linear time to solve the general all-ones problem for trees. The first one is good for counting the number of solutions if solutions do exist, and the second one is good for solving the minimum all-ones problem. Furthermore, we can modify the algorithm slightly to solve the general minimum all-ones problem. [Copyright &y& Elsevier]

Abstract: Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program. [Copyright &y& Elsevier]

Abstract: The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions. [Copyright &y& Elsevier]

Abstract: This paper concerns improper -colourings of graphs and focuses on the sizes of the monochromatic components (i.e., components of the subgraphs induced by the colour classes). Consider the following three simple operations, which should, heuristically, help reduce monochromatic component size: (a) assign to a vertex the colour that is least popular among its neighbours; (b) change the colours of any two adjacent differently coloured vertices, if doing so reduces the number of monochromatic edges; and (c) change the colour of a vertex, if by so doing you can reduce the size of the largest monochromatic component containing it without increasing the number of monochromatic edges. If a colouring cannot be further improved by these operations, then we regard it as locally optimal. We show that, for such a locally optimal 2-colouring of a graph of maximum degree 4, the maximum monochromatic component size is . The operation set (a)–(c) appears to be one of the simplest that achieves a bound on monochromatic component size. Recent work by Alon, Ding, Oporowski and Vertigan, and then Haxell, Szabó and Tardos, has shown that some algorithms can do much better, achieving a constant bound on monochromatic component size. However, the simplicity of our operation set, and of the associated local search algorithm, make the algorithm, and our locally optimal colourings, of interest in their own right. [Copyright &y& Elsevier]

Double-loop networks have been widely studied as architecture for local area networks and it is well-known that the minimum distance diagram of a double-loop network yields an L-shape. Given an N, it is desirable to find a double-loop network DL(N;s1,s2) with its diameter being the minimum among all double-loop networks with N stations. Since the diameter can be easily computed from an L-shape, one method is to start with a desirable L-shape and then asks whether there exist s1 and s2 (also called the steps of the double-loop network) to realize it. In this paper, we propose a simple and efficient algorithm to find s1 and s2, which is based on the Smith normalization method of Aguilo´, Esque´ and Fiol. [Copyright &y& Elsevier]