Search

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

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 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: In this paper, we analyze an algorithm to compute a low-rank approximation of the similarity matrix introduced by Blondel et al. in [1]. This problem can be reformulated as an optimization problem of a continuous function where S is constrained to have unit Frobenius norm, and is a non-negative linear map. We restrict the feasible set to the set of matrices of unit Frobenius norm with either k nonzero identical singular values or at most k nonzero (not necessarily identical) singular values. We first characterize the stationary points of the associated optimization problems and further consider iterative algorithms to find one of them. We analyze the convergence properties of our algorithm and prove that accumulation points are stationary points of . We finally compare our method in terms of speed and accuracy to the full rank algorithm proposed in [1]. [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: 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 focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in -time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of of the optimum in -time, where is the minimum k such that there is a spanning tree of the graph with maximum degree k. [Copyright &y& Elsevier]

Abstract: The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of -colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. [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: A minus clique-transversal function of a graph is a function such that for every clique C of G. The weight of a minus clique-transversal function is , over all vertices . The minus clique-transversal number of a graph G, denoted , equals the minimum weight of a minus clique-transversal function of G. The upper minus clique-transversal number of a graph G, denoted , equals the maximum weight of a minimal minus clique-transversal function of G. In this paper, we show that the minus clique-transversal problem (respectively, upper minus clique-transversal problem) is NP-complete even when restricted to chordal graphs. On the other hand, we give a linear algorithm to solve the minus clique-transversal problem for block graphs. [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: The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink. [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]

In this paper, we study finite orders whose comparability graphs are split graphs. We introduce a normalized representation of these orders using a family of open real intervals. Its repercussions are both structural and algorithmic. We show that the dimension of split orders is at most three, and we give a simple characterization of those of dimension two. We present a linear time recognition algorithm for directed graphs whose transitive closures are split orders. [Copyright &y& Elsevier]

Splitting off a pair of edges su, sv in a graph G means replacing these two edges by a new edge uv. This operation is well known in graph theory. Let G=(V+s,E+F) be a graph which is k-edge-connected in V and suppose that |F| is even. Here F denotes the set of edges incident with s. Lova´sz (Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979) proved that if k⩾2 then the edges in F can be split off in pairs preserving the k-edge-connectivity in V. This result was recently extended to the case where a bipartition R∪Q=V is given and every split edge must connect R and Q (SIAM J. Discrete Math. 12 (2) (1999) 160). In this paper, we investigate an even more general problem, where two disjoint subsets R,Q⊂V are given and the goal is to split off (the largest possible subset of) the edges of F preserving k-edge-connectivity in V in such a way that every split edge incident with a vertex from R has the other end-vertex in Q. Motivated by connectivity augmentation problems, we introduce another extension, the so-called split completion version of our problem. Here, the smallest set F* of edges incident to s has to be found for which all the edges of F+F* can be split off in the augmented graph G=(V+s, E+F+F*) preserving k-edge-connectivity and in such a way that every split edge incident with a vertex from R has the other end-vertex in Q. We solve each of the above extensions when k is even: we give min–max formulae and polynomial algorithms to find the optima. For the case when k is odd we show how to find a solution to the split completion problem using at most two edges more than the optimum. [Copyright &y& Elsevier]