Search

Abstract: This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices and . This route can be a walk, a trail or a path. Each time a vertex is crossed by a walk there is an associated non-negative reload cost , where and denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimum. Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., ) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs. [Copyright &y& Elsevier]

Abstract: The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded tree-width graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators. [Copyright &y& Elsevier]

Abstract: This paper introduces a novel approach to the task of lexical translation between languages for which no translation dictionaries are available. We build a massive translation graph, automatically constructed from over 630 machine-readable dictionaries and Wiktionaries. In this graph each node denotes a word in some language and each edge denotes a word sense shared by and . Our current graph contains over 10,000,000 nodes and expresses more than 60,000,000 pairwise translations. The composition of multiple translation dictionaries leads to a transitive inference problem: if word A translates to word B which in turn translates to word C, what is the probability that C is a translation of A? The paper describes a series of probabilistic inference algorithms that solve this problem at varying precision and recall levels. All algorithms enable us to quantify our confidence in a translation derived from the graph, and thus trade precision for recall. We compile the results of our best inference algorithm to yield PanDictionary, a novel multilingual dictionary. PanDictionary contains more than four times as many translations as in the largest Wiktionary at precision 0.90 and over 200,000,000 pairwise translations in over 200,000 language pairs at precision 0.8. [Copyright &y& Elsevier]

Abstract: Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with vertices and dominating number can be solved in time using tree/branch-decomposition based algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time and memory space for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink such that (i) for each vertex the sum of the transit times of arcs on any path from to takes the same value, and (ii) for each vertex the minimum - cut is determined by the arcs incident to whose tails are reachable from . This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem. [Copyright &y& Elsevier]

Abstract: The -median problem on a tree is to find a set of vertices on that minimizes the sum of distances from ’s vertices to . In this paper, we study two generalizations of the 2-median problem, which are obtained by imposing constraints on the two vertices selected as a 2-median: one is to limit their distance while the other is to limit their eccentricity. Previously, both the best upper bounds of these two generalizations were [A. Tamir, D. Perez-Brito, J.A. Moreno-Perez, A polynomial algorithm for the -centdian problem on a tree, Networks 32 (1998) 255–262; B.-F. Wang, S.-C. Ku, K.-H. Shi, Cost-optimal parallel algorithms for the tree bisector problem and applications, IEEE Transactions on Parallel and Distributed Systems 12 (9) (2001) 888–898]. In this paper, we solve both in time. We also study cases when linear time algorithms exist for the two generalizations. For example, we solve both in linear time when edge lengths and vertex weights are all polynomially bounded integers. Furthermore, we consider the relaxation of the two generalized problems by allowing 2-medians on any position of edges, instead of just on vertices, and we give -time algorithms for them. A problem, named the tree marker problem, arises several times in our approaches to the two generalized 2-median problems, and we give an -time algorithm for this problem. We also use this algorithm to speedup an algorithm of Gupta and Punnen [S.K. Gupta, A.P. Punnen, Group center and group median of a tree, European Journal of Operational Research 65 (1993) 400–406] for the group median problem, improving the running time from to , where is the number of groups in the input. [Copyright &y& Elsevier]

Abstract: This paper deals with the mathematical properties of watersheds in weighted graphs linked to region merging methods, as used in image analysis. In a graph, a cleft (or a binary watershed) is a set of vertices that cannot be reduced, by point removal, without changing the number of regions (connected components) of its complement. To obtain a watershed adapted to morphological region merging, it has been shown that one has to use the topological thinnings introduced by M. Couprie and G. Bertrand. Unfortunately, topological thinnings do not always produce thin clefts. Therefore, we introduce a new transformation on vertex weighted graphs, called C-watershed, that always produces a cleft. We present the class of perfect fusion graphs, for which any two neighboring regions can be merged, while preserving all other regions, by removing from the cleft the points adjacent to both. An important theorem of this paper states that, on these graphs, the C-watersheds are topological thinnings and the corresponding divides are thin clefts. We propose a linear-time immersion-like algorithm to compute C-watersheds on perfect fusion graphs, whereas, in general, a linear-time topological thinning algorithm does not exist. Furthermore, we prove that this algorithm is monotone in the sense that the vertices are processed in increasing order of weight. Finally, we derive some characterizations of perfect fusion graphs based on the thinness properties of both C-watersheds and topological watersheds. [Copyright &y& Elsevier]

Abstract: The paper proposes a methodology to assist the designer at the initial stages of the design synthesis process by enabling him/her to employ knowledge and algorithms existing in graph network theory. The proposed method comprises three main stages: transforming the synthesis problem into a graph theoretic problem; devising the topology possessing special engineering properties corresponding to the system requirements; finding the geometric configuration of that topology that will possess the desired properties. To clarify the idea and to demonstrate its generality, the approach is presented through three synthesis case studies from different engineering domains: electrical networks, statics and kinematics. As is highlighted in the paper, the approach of employing graph theory in the synthesis process offers several unique advantages. Among these advantages are: gaining a general perspective on different synthesis problems from different engineering domains by transforming them into the same graph problem; employing the same graph algorithms for different synthesis problems; establishing the existence of configurations with special properties solely from the topology of the system; transferring knowledge and methods between different engineering disciplines for both the topology and the geometry generation steps. [Copyright &y& Elsevier]

Abstract: The interconnection network considered in this paper is the folded hypercube that is an attractive variance of the well-known hypercube. The folded hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. In this paper, we study the path embedding aspects, bipanconnectivity and -panconnectivity, of the -dimensional folded hypercube. A bipartite graph is bipanconnected if each pair of vertices and are joined by the bipanconnected paths that include a path of each length satisfying and is even, where is the number of vertices, and denotes the shortest distance between and . A graph is -panconnected if each pair of vertices and are joined by the paths that include a path of each length ranging from to . In this paper, we introduce a new graph called the Path-of-Ladders. By presenting algorithms to embed the Path-of-Ladders into the folded hypercube, we show that the -dimensional folded hypercube is bipanconnected for is an odd number. We also show that the -dimensional folded hypercube is strictly -panconnected for is an even number. That is, each pair of vertices are joined by the paths that include a path of each length ranging from to ; and the value reaches the lower bound of the problem. [Copyright &y& Elsevier]

Abstract: The main focus of this paper is the analysis of a simple randomized scheme for constructing low-weight -connected spanning subgraphs. In this paper, we focus on the metric graph. We use the term metric graph for a complete graph with metric weights. We first show that our scheme gives a simple approximation algorithm to construct a minimum-weight -connected spanning subgraph in a metric graph, an -hard problem. We show that our algorithm gives an approximation ratio of for a metric graph, for a random graph with nodes uniformly randomly distributed in and for a complete graph with random edge weights . We show that our scheme is optimal with respect to the amount of “local information” needed to compute any connected spanning subgraph. We then show that our scheme can be applied to design an efficient distributed algorithm for constructing such an approximate -connected spanning subgraph (for any ) in a point-to-point distributed model, where the processors form a complete network. Our algorithm takes time and an expected number of messages. Our result in conjunction with a result of Korach et al. [E. Korach, S. Moran, S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, SIAM Journal on Computing 16 (2) (1987) 231–236] implies that the expected message complexity of our algorithm is significantly better than the best distributed algorithm that finds an optimal -connected subgraph. We also show that for geometric instances, our randomized scheme constructs low-degree -connected spanning subgraphs which have maximum degree, with high probability. [Copyright &y& Elsevier]

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph with a cost function and two subsets and satisfying , a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in such that each vertex in cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a-approximation algorithm for the problem, where is the best-known approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in worst-case time, which allowed it to be integrated as part of an time all-pairs algorithm. Here and respectively denote the number of edges and vertices in the graph, while denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just time. This can be integrated as part of the time spent solving single-source, improving on the value of obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in time and included as part of the time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from to . [Copyright &y& Elsevier]

Abstract: Given a finite set , and a hypergraph , the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for . This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618–628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time. More generally, we consider a monotone property over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50–63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying and all maximal subsets not satisfying , for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties . [Copyright &y& Elsevier]

Abstract: Given a graph , a subgraph is a k-spanner of G if for any pair of vertices it satisfies . The basic k-spanner problem is to find a k-spanner of a given graph G with the smallest possible number of edges. This paper considers approximation algorithms for this and some related problems for , known to be -inapproximable. The basic k-spanner problem over undirected graphs with has been given a sublinear ratio approximation algorithm (with ratio roughly ), but no such algorithms were known for other variants of the problem, including the directed and the client–server variants, as well as for the related k-DSS problem. We present the first approximation algorithms for these problems with sublinear approximation ratio. The second contribution of this paper is in characterizing some wide families of graphs on which the problems do admit a logarithmic and a polylogarithmic approximation ratios. These families are characterized as containing graphs that have optimal or “near-optimal” spanners with certain desirable properties, such as being a tree, having low arboricity or having low girth. All our results generalize to the directed and the client–server variants of the problems. As a simple corollary, we present an algorithm that given a graph G builds a subgraph with edges and stretch bounded by the tree-stretch of G, namely the minimum maximal stretch of a spanning tree for G. The analysis of our algorithms involves the novel notion of edge-dominating systems developed in the paper. The technique introduced in the paper reduces the studied algorithmic approximability questions on k-spanners to purely graph-theoretical questions concerning the existence of certain combinatorial objects in families of graphs. [Copyright &y& Elsevier]

Abstract: Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than π). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces. These constraints are described by combinatorial pseudo-triangulations, first defined and studied in this paper. Also of interest are our two proof techniques, one based on Henneberg inductive constructions from combinatorial rigidity theory, the other on a generalization of Tutte''s barycentric embeddings to directed 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]

This paper presents a new approach to algorithm design and analysis that benefits from the OO characteristics of Java. It consists of first defining the inheritance structure of a collection of algorithms, at different levels of abstraction. Then, correctness proofs and complexity measures are designed for the various levels of abstraction. The goal is to prove as many properties as possible at each abstract level, assuming the implementations of the methods called upon will be correct. Thus, when a more specialized algorithm is derived from a more abstract one, proofs and complexity analysis can be reused, and simply need to be completed by proving that the properties assumed for the concrete methods indeed hold. The approach is illustrated with several inheritance trees: for sorting, graph algorithms, string matching, and network flow. Each tree, at the bottom of the hierarchy, yields well-known algorithms in the respective area. Instead of using pseudo-code to describe these trees, Java is used to make the process more precise and useful, encouraging the design and analysis of algorithms, and also experimentation with new variants. The implementation presented in this paper takes advantage of Java’s organization to build the inheritance trees for the classes, and Java’s interfaces, collections, comparators, and iterators. [Copyright &y& Elsevier]

We characterize the structure of null spaces of symmetric diagonally dominant (SDD) matrices and symmetric H-matrices with non-negative diagonal entries. We show that the structure of the null space of a symmetric SDD matrix or H-matrix A depends on the structure of the connected components of its underlying graph. Each connected component contributes at most one vector to the null space. This paper provides a combinatorial characterization of the rank of each connected component, and a combinatorial characterization of a null vector if one exists. For SDD matrices, we also present an efficient combinatorial algorithm for constructing an orthonormal basis for the null space.The paper also shows a close connection between gain graphs and H-matrices, which extends known results regarding the connection between undirected graphs and Laplacian matrices, and between signed graphs and SDD matrices.We show how to exploit these combinatorial algorithms to reliably solve certain singular linear systems in finite-precision arithmetic. [Copyright &y& Elsevier]

Many vertex-partitioning problems can be expressed within a general framework introduced by Telle and Proskurowski. They showed that optimization problems in this framework can be solved in polynomial time on classes of graphs with bounded tree-width. In this paper, we consider a very similar framework, in relationship with more general classes of graphs: we propose a polynomial time algorithm on classes of graphs with bounded clique-width for all the optimization problems in our framework. These classes of graphs are more general than the classes of graphs with bounded tree-width in the sense that classes of graphs with bounded tree-width have also bounded clique-width (but not necessarily the inverse).Our framework includes problems such as independent (dominating) set, p-dominating set, induced bounded degree subgraph, induced p-regular subgraph, perfect matching cut, graph k-coloring and graph list-k-coloring with cardinality constraints (fixed k). This paper thus provides a second (distinct) framework within which the optimization problems can be solved in polynomial time on classes of graphs with bounded clique-width, after a first framework (called MS1) due to the work of Courcelle, Makowsky and Rotics (for which they obtained a linear time algorithm). [Copyright &y& Elsevier]

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]

A many-to-many k -disjoint path cover ( k -DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T , each of size k , is a collection of k vertex-disjoint paths between S and T , which altogether cover every vertex of G . This is classified as paired , if each vertex of S must be joined to a specific vertex of T , or unpaired , if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired k - DPC problem on a unit interval graph is polynomially solvable for any fixed k . [ABSTRACT FROM AUTHOR]

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

The scientific literature teems with clique-centric clustering strategies. In this paper we analyze one such method, the paraclique algorithm. Paraclique has found practical utility in a variety of application domains, and has been successfully employed to reduce the effects of noise. Nevertheless, its formal analysis and worst-case guarantees have remained elusive. We address this issue by deriving a series of lower bounds on paraclique densities. [ABSTRACT FROM AUTHOR]

In this paper, we study the competition graphs of oriented complete bipartite graphs. We characterize graphs that can be represented as the competition graphs of oriented complete bipartite graphs. We also present the graphs having the maximum number of edges and the graphs having the minimum number of edges among such graphs. [ABSTRACT FROM AUTHOR]

The average eccentricity e c c ( G ) of a graph G is the mean value of eccentricities of all vertices of G . In this paper, we continue the work of Ilić (2012) and resolve a conjecture, obtained by the system AutoGraphiX, about the upper bound on the sum of the average eccentricity and the domination number among connected graphs on n vertices. [ABSTRACT FROM AUTHOR]

An r -dynamic k -coloring of a graph G is a proper vertex k -coloring of G such that the neighbors of any vertex v receive at least min { r , deg ( v ) } different colors. The r -dynamic chromatic number of G , χ r ( G ) , is defined as the smallest k such that G admits an r -dynamic k -coloring. In this paper, first we introduce an upper bound for χ r ( G ) in terms of r , chromatic number, maximum degree and minimum degree. Then, motivated by a conjecture of Montgomery (2001) stating that for a d -regular graph G , χ 2 ( G ) − χ ( G ) ≤ 2 , we prove two upper bounds for χ 2 − χ on regular graphs. Our first upper bound ⌈ 5.437 log d + 2.721 ⌉ improves a result of Alishahi (2011). Also, our second upper bound shows that Montgomery’s conjecture is implied by the existence of a χ ( G ) -coloring for any regular graph G , such that any two vertices whose neighbors are unicolored in this coloring, have no common neighbor. [ABSTRACT FROM AUTHOR]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G . [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph G ̃ , produces the directed Cartesian-product decomposition of G in linear time. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph. [ABSTRACT FROM AUTHOR]

Given two positive integers l and m , with l ≤ m , an [ l , m ] - covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l ≤ | M | ≤ m for every M ∈ M . An [ l , m ] -covering M of G is an excessive [ l , m ] - factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [ l , m ] -factorization of G (or ∞ , if G does not admit an excessive [ l , m ] -factorization) is a graph parameter called the excessive [ l , m ] - index of G and denoted by χ [ l , m ] ′ ( G ) . In this paper we study such parameter. Our main result is a general formula for the excessive [ l , m ] -index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ [ l , m ] ′ ( G ) for any fixed constants l and m and outputs an excessive [ l , m ] -factorization of G , whenever the latter exists. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m + n 3 + r branchings that makes at most m ( m + n 3 + r ) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m + r − 1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m + r − 1 branchings and makes at most ( m + r + 2 ) n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m − n + 2 arborescences–thus improving the bound of m of Leston-Rey and Wakabayashi–and makes at most ( m − n + 5 ) n oracle calls. [ABSTRACT FROM AUTHOR]

Suppose that we are given two independent sets I b and I r of a graph such that | I b | = | I r | , and imagine that a token is placed on each vertex in I b . Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I b into I r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I b and I r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. [ABSTRACT FROM AUTHOR]

A dominating induced matching , also called an efficient edge domination , of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F ⊆ E of edges in the graph such that no two edges in F share a common endpoint and each edge in E ∖ F is incident with exactly one edge in F . It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.146 7 n n O ( 1 ) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F , where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some “good vertices,” branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new concept of saturated vertices for the alliances. For a given graph G = ( V , E ) and S ⊂ V , a vertex v ∈ V is said to be S -saturated , if the number of its defenders is equal to the number of its attackers for S . We define new parameters | λ ( S ) | and | λ ̄ ( S ) | as the number of S -saturated vertices and not S -saturated vertices of S , respectively. We study mathematical properties of (global) saturated boundary defensive, offensive and powerful k -alliances and theoretical results are obtained by giving in particular some tight bounds and exact values on the cardinality of such alliances. As a main result, we give tight bounds for the cardinality of every minimal global boundary powerful ( − 1 ) -alliance (MGBPA) in terms only of the order and the size of graph. Furthermore, we establish two algorithms which generate graphs containing (connected) MGBPA from a given complete graph K 2 n . [ABSTRACT FROM AUTHOR]

We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k - limited packing if for every vertex v ∈ V ( G ) , | N [ v ] ∩ X | ≤ k , where N [ v ] is the closed neighbourhood of v . The k - limited packing number L k ( G ) of a graph G is the largest size of a k -limited packing in G . Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k -limited packing number and a randomized algorithm to find k -limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree Δ , L k ( G ) ≥ k n ( k + 1 ) ( Δ k ) ( Δ + 1 ) k . Also, some other upper and lower bounds for L k ( G ) are given. [ABSTRACT FROM AUTHOR]

In the game of Kayles , two players select alternatingly a vertex from a given graph G , but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = ( V , E ) , if G [ W ] is connected and there exists an independent set X such that W = V − N [ X ] . The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G . We prove that the number of K-sets in a graph with n vertices is bounded by O ( 1.6052 n ) . A computer-generated case analysis improves this bound to O ( 1.6031 n ) K-sets, and thus we have an upper bound of O ( 1.6031 n ) on the running time of the algorithm for Kayles . We also show that the number of K-sets in a tree is bounded by n ⋅ 3 n / 3 and thus Kayles can be solved on trees in O ( 1.4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G avoid ( POS DNF 2 ) and G seek ( POSDNF 3 ) can also be determined in O ( 1.6031 n ) time. In G avoid ( POSDNF 2 ) , we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game G seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. [ABSTRACT FROM AUTHOR]

A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges ( → B 1 -EPG); (ii) the paths on the grid are not bended and the intersections concern vertices ( → B 0 -VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B 1 -EPG cographs and B 0 -VPG cographs using their cotree. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R 2 . First, we propose an O ( n 2 log n ) time in-place algorithm for finding the maximum clique of the intersection graph of a set of n axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to O ( n log n + n K ) , where K is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is O ( m log n + n 2 ) where m is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is O ( n 2 + m ( n + K 3 ) ) ; m is the number of edges in the unit disk intersection graph and K is the size of the largest clique in that graph. It uses O ( n 3 ) time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in O ( 1 ) time. This problem is of independent interest. All these algorithms need O ( 1 ) work space in addition to the input array. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . The cardinality of a minimum k -path vertex cover is called the k -path vertex cover number of a graph G , denoted by ψ k ( G ) . It is known that the minimum k -path vertex cover problem ( k -PVCP) is NP-hard for all k ≥ 2 . In this paper we consider the weighted version of a k -PVCP ( k -WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P k . This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k -WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k -path vertex cover number of a tree with time complexity O ( k ⋅ | V ( G ) | ) is presented. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the much studied problem of Pattern Matching with Swaps (Swap Matching problem, for short). We first present a graph-theoretic model, which opens a new and so far unexplored avenue to solve the problem. Then, using the model, we devise two efficient algorithms to solve the swap matching problem. The resulting algorithms are adaptations of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, both the algorithms run in linear time considering a fixed alphabet. [ABSTRACT FROM AUTHOR]

Given a connected outerplanar graph G of pathwidth p , we give an algorithm to add edges to G to get a supergraph of G , which is 2-vertex-connected, outerplanar and of pathwidth O ( p ) . This settles an open problem raised by Biedl [1] , in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. [ABSTRACT FROM AUTHOR]

In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O ( m ϵ 4.5 T ) space and outputs a ( 1 + ϵ ) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman et al. [2] , which distinguishes between triangle-free graphs and graphs with at least T triangles using O ( m T 1 / 3 ) space. Also, in terms of dependence on T , we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O ( m T 1 / 2 + ρ ) space for any constant ρ ≥ 0 . [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, set graphs are the underlying graphs of digraph representations of hereditarily finite sets, where a set is hereditarily finite if it is finite and has only hereditarily finite sets as members. It is known that every connected -free (or claw-free) graph is a set graph, and that an extensional acyclic orientation of such a graph can be found in polynomial time. In this paper, we generalize this result in three different directions. First, we identify the largest hereditary class of graphs such that for every connected induced subgraph of , it holds that is a set graph if and only if it is claw-free. Second, we consider graphs in which no two distinct induced claws have equal or adjacent centers, and prove that in this class of graphs set graphs can be equivalently characterized in terms of a property related to successive vertex removal. Finally, we show that for every , connected -free graphs admit an acyclic orientation that is -extensional, in the sense that at most distinct vertices can have the same out-neighborhood. This also leads to a simple linear time algorithm for finding an extensional acyclic orientation of a given connected claw-free graph, thus improving over the previous algorithm. [Copyright &y& Elsevier]

Current dominant methods for slope stability analysis are the limit equilibrium method and the strength reduction method. Both methods are based on the limit equilibrium conditions. However, the limit equilibrium methods are limited to the rigid body assumption, while the strength reduction method is computationally expensive and has convergence issues due to the non-linear iterative computations. In this paper, we propose a current stress-based search algorithm to directly obtain the critical slip surface and the safety factor. The numerical manifold method, which unifies the continuum and discontinuum analysis problems, is used for stress analysis to obtain the stress distribution of soil slopes or rock slopes cut by joints. Based on the stress results obtained, a graph theory is used to convert the solution of the critical slip surface to a shortest path problem, which can be directly solved by the Bellman-Ford algorithm. The proposed method couples the numerical manifold method and the graph theory allowing for stability analyses of both rock and soil slopes within the same framework. The method completely removes the computational effort needed for iterations in the strength reduction method as well as eliminating the rigid body assumptions in the limit equilibrium method. [ABSTRACT FROM AUTHOR]

Abstract: The topological containment problem, TC( ), has been shown to be polynomial-time solvable for any fixed pattern graph , but practical algorithms have been developed only for a few specific pattern graphs. Among these are the wheels with four, five, and six spokes. This paper examines the topological containment problem where the pattern graph is a wheel with seven spokes, and gives a result that describes graphs with no -subdivision, showing how they can be built up, using certain operations, from smaller ‘pieces’ that meet certain conditions. We also discuss algorithmic aspects of the problem. [Copyright &y& Elsevier]

Abstract: A subset of the vertex set of a graph is a secure dominating set of if is a dominating set of and if, for each vertex not in , there is a neighbouring vertex of in such that the swap set is again a dominating set of . The secure domination number of , denoted by , is the cardinality of a smallest secure dominating set of . A linear algorithm is proposed in this paper for finding a minimum secure dominating set and hence the value for a tree . The algorithm is based on a strategy of repeatedly pruning away pendent spiders of after having dominated them securely. [Copyright &y& Elsevier]

Abstract: A hypergraph is a set family defined on vertex set . The dual of is the set of minimal subsets of such that for any . The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time. [Copyright &y& Elsevier]

Abstract: A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs still remain long-standing open problems. The present paper gives characterizations for co-bipartite opposition graphs and co-bipartite coalition graphs, and for bipartite opposition graphs. Implicit in our argument is a linear time recognition algorithm for these graphs. As an interesting by-product, we find new submatrix characterizations for the well-studied bipartite permutation graphs. [Copyright &y& Elsevier]