Search

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

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]

Abstract: In this paper, we present algorithms that compute large matchings in planar graphs with fixed minimum degree. The algorithms give a guarantee on the size of the computed matching and run in linear time. Thus they are faster than the best known algorithm for computing maximum matchings in general graphs and in planar graphs, which run in and time, respectively. For the class of planar graphs with minimum degree 3, the bounds we achieve are known to be the best possible. Further, we discuss how minimum degree 5 can be used to obtain stronger bounds on the matching size. [Copyright &y& Elsevier]

Abstract: Let be a connected graph with vertices. Let be an integer. Suppose that a fire breaks out at a vertex of . A firefighter starts to protect vertices. At each time interval, the firefighter protects -vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn denote the maximum number of vertices in that the firefighter can save when a fire breaks out at vertex . The -surviving rate of is defined to be , which is the average proportion of saved vertices. In this paper, we investigate the surviving rate of outerplanar graphs with vertices. The main results are as follows: (1) ; and (2) if , and if , which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814–1826]. [ABSTRACT FROM AUTHOR]

Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, and , with domain sizes and , respectively, and the same range, the goal of the problem is to find and such that . This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of functions for any constant integer , where the domain sizes of the functions may be different. [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [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: In this paper, we consider the undirected version of the well known maximum edge-disjoint paths problem, restricted to complete graphs. We propose an off-line 3.75-approximation algorithm and an on-line 6.47-approximation algorithm, improving the earlier 9-approximation algorithm proposed by Carmi, Erlebach, and Okamoto [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143–155]. Moreover, we show that for the general case, no on-line algorithm is better than a -approximation, for all . For the special case when the number of paths is within a linear factor of the number of vertices of the graph, it is established that the problem can be optimally solved in polynomial time by an off-line algorithm, but that no on-line algorithm is better than a -approximation. Finally, the proposed techniques are used to obtain off-line and on-line algorithms with a constant approximation ratio for the related problems of edge congestion routing and wavelength routing in complete graphs. [Copyright &y& Elsevier]

Abstract: We consider semistructured data as multirooted edge-labelled directed graphs, and path inclusion constraints on these graphs. A path inclusion constraint is satisfied by a semistructured data if any node reached by the regular query is also reached by the regular query . In this paper, two problems are mainly studied: the implication problem and the problem of the existence of a finite exact model. [–] We give a new decision algorithm for the implication problem of a constraint by a set of bounded path constraints where , , and the ’s are regular path expressions and the ’s are words, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and N. Alechina et al. In the case of a set of word equalities , we provide a more efficient decision algorithm for the implication of a word equality , improving the more general algorithm of P. Buneman et al. We prove that, in this case, implication for nondeterministic models is equivalent to implication for (complete) deterministic ones. [–] We introduce the notion of exact model: an exact model of a set of path constraints satisfies the constraint if and only if this constraint is implied by . We prove that any set of constraints has an exact model and we give a decidable characterization of data which are exact models of bounded path inclusion constraints sets. [Copyright &y& Elsevier]

Abstract: Given a graph , the problem is to determine an acyclic orientation of which minimizes the maximal number of changes of orientation along any shortest path in . The corresponding value is called the rank of the graph . The motivation for this graph theoretical problem comes from the design of deadlock-free packet routing protocols [G. Tel, Deadlock-free packet switching networks, in: Introduction to Distributed Algorithms, Cambridge University Press, Cambridge, UK, 1994 (Chapter 5)]. This acyclic orientation covering problem on the shortest path systems has been studied in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] where it was shown that the general problem of determining the rank is NP-complete and some upper and lower bounds on the rank were presented for particular topologies, such as grids, tori and hypercubes. The main unresolved problem stated in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] was to determine the rank values for other well-known interconnection networks and also for more general classes of graphs. In this paper we give a general lower bound argument for the rank problem and apply it to the class of involution-generated Cayley graphs which among others include hypercubes, star graphs, pancake graphs and transposition-tree based graphs [S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38 (4) (1989) 555–565]. We also present a large class of graphs with constant rank. This class of graphs is defined as the layered cross product [S. Even, A. Litman, Layered cross product—A technique to construct interconnection networks, Networks 29 (1997) 219–223] of layered trees and series–parallel graphs and includes among others butterflies, Beneš networks, fat-trees and meshes of trees. For some special topologies, improved lower bounds on the rank are also presented. We consider some of the modified versions of the rank problem as well. [Copyright &y& Elsevier]