Search

Abstract: Finding the lowest common ancestor (LCA) of two nodes in a binary tree has been focused both in graph theory and computer science. The paper puts forward and proves an analytic criterion for the LCA of two neighboring nodes in a complete binary tree. The criterion mainly concerns addition, subtraction and bitwise operations, needs no searching procedures and thus is easy to implement in software programming as well as hardware programming. An algorithm that has logarithmic time complexity is also presented with C-language implementation in the paper. [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: 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]

Anchorgraph based learning methods have met with success in modeling the large data for scalable semi-supervised learning. However, like most graph based learning algorithms, they are usually built with a randomly selected labeled set classified in advance. Although many pool-based active learning methods have been proposed, they often require a relatively large computational and storage consumption, which tends to impose extra burden on the learning system. Thus in this paper, we propose a novel active learning method named anchor-based transductive experimental design (ATED). By fully utilizing the representing power of anchors, the improved method efficiently enhances the performance of the original anchorgraph based learning while introduces much less extra cost on computation and storage. Extensive experimental results on real-world datasets have validated our approach in terms of classifying accuracy and computational efficiency. [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]

Abstract: Finding shortest paths is a fundamental problem in graph theory, which has a large amount of applications in many areas like computer science, operations research, network routing and network analysis. Although many exact and approximate algorithms have been proposed, it is still a time-consuming task to calculate shortest paths for large-scale networks with tremendous volume of data available in recent years. In this paper, we find that the classic Dijkstra''s algorithm can be improved by simple modification. We propose a fast algorithm which utilize the preiously-calculated results to accelerate the latter calculation. Simple optimization strategies are also proposed with consideration of characteristics of scale-free complex networks. Our experimental results show that the average running time of our algorithm is lower than the Dijkstra''s algorithm by a factor relating to the connection probability in random networks of ER model. The performance of our algorithm is significantly better than the Dijkstra''s algorithm in scale-free networks generated by the AB model. The results show that the time complexity is reduced to about O(n2.4) in scalefree complex networks. When the optimization strategies are applied, the algorithm performance is further improved slightly in scale-free networks. [Copyright &y& Elsevier]

Abstract: Multi-scale gist (MS-gist) feature manifold for building recognition is presented in the paper. It is described as a two-stage model. In the first stage, we extract the multi-scale gist features that represent the structural information of the building images. Since the MS-gist features are extrinsically high dimensional and intrinsically low dimensional, in the second stage, an enhanced fuzzy local maximal marginal embedding (EFLMME) algorithm is proposed to project MS-gist feature manifold to low-dimensional subspace. EFLMME aims to preserve local intra-class geometry and maximize local interclass margin separability of MS-gist feature manifold of different classes at the same time. To evaluate the performance of our proposed model, experiments were carried out on the Sheffield buildings database, compared with the existing works: (a) the visual gist based building recognition model (VGBR) and (b) the hierarchical building recognition model (HBR). Moreover, EFLMME is evaluated on Sheffield buildings database compared with some linear dimensionality reduction methods. The results show that the proposed model is superior to other models in practice of building recognition and can handle the building recognition problem caused by rotations, variant lighting conditions and occlusions very well. [Copyright &y& Elsevier]

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]

We show that good community structures can be obtained by partitioning a social network in a succession of divisive sparsest cuts. A network flow algorithm based on fundamental principles of graph theory is introduced to identify the sparsest cuts and an underlying hierarchical community structure of the network via maximum concurrent flow. Matula [Matula, David W., 1985. Concurrent flow and concurrent connectivity in graphs. In: Alavi, Y., et al. (Eds.), Graph Theory and its Applications to Algorithms and Computer Science. Wiley, New York, NY, pp. 543–559.] established the maximum concurrent flow problem (MCFP), and papers on divisive vs. agglomerative average-linkage hierarchical clustering [e.g., Matula, David W., 1983. Cluster validity by concurrent chaining. In: Felsenstein, J. (Ed.), Numerical Taxonomy: Proc. of the NATO Adv. Study Inst., vol. 1. Springer-Verlag, New York, pp. 156–166 (Proceedings of NATO ASI Series G); Matula, David W., 1986. Divisive vs. agglomerative average linkage hierarchical clustering. In: Gaul, W., and Schader, M. (Eds.), Classification as a Tool of Research. Elsevier, North-Holland, Amsterdam, pp. 289–301; Thompson, Byron J., 1985. A flow rerouting algorithm for the maximum concurrent flow problem with variable capacities and demands, and its application to cluster analysis. Master Thesis. School of Engineering and Applied Science, Southern Methodist University] provide the basis for partitioning a social network by way of sparsest cuts and/or maximum concurrent flow. The MCFP extends the [Ford Jr., Lester R., Fulkerson, Delbert R., 1956. Maximal flow through a network. Canadian Journal of Mathematics 8, 399–404; Ford Jr., Lester R., Fulkerson, Delbert R., 1962. Flows in Networks. Princeton University Press, Princeton, NJ] source–sink max-flow problem to all-pairs maximum concurrent flow. The density of an (S, T)-cut is |(S, T)\/(|S|•|T|) where |(S, T)| is the number of edges (equivalently, links or bonds) between communities S and T with |S|•|T| being the maximum number of edges possible. The minimum density cut in the network is the sparsest cut. When the edges are weighted, the density is the average weight of the (S, T)-cut edges, with absent edges treated as edges of zero weight. Sparsest cuts (i.e., minimum density) of the remaining components are iteratively determined via linear programming until a multipartite cut is identified that is more constraining to concurrent flow than any sparsest cut. Empirical results on real-world networks with known hierarchical structures and random networks with embedded communities are used to compare this sparsest-cut community structure criterion to the weighted Girvan–Newman community structure criterion [e.g., Newman, M.E.J., 2004. Analysis of weighted networks. Physical Review E 70, 056131] that is based on edge betweenness centrality. A new measure of accuracy M is defined to evaluate the results of the graph partitionings found by these criteria. [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: Many well-known problems in Artificial Intelligence can be formulated in terms of systems of constraints. The problem of testing the satisfiability of propositional formulae (SAT) is of special importance due to its numerous applications in theoretical computer science and Artificial Intelligence. A brute-force algorithm for SAT will have exponential time complexity , where is the number of Boolean variables of the formula. Unfortunately, more sophisticated approaches such as resolution result in similar performances in the worst case. In this paper, we present a simple and relatively efficient parallel divide-and-conquer method to solve various subclasses of SAT. The dissection stage of the parallel algorithm splits the original formula into smaller subformulae with only a bounded number of interacting variables. In particular, we derive a parallel algorithm for the class of formulae whose corresponding graph representation is planar. Our parallel algorithm for planar 3-SAT has the worst-case performance of on a PRAM (parallel random access model) computer. Applications of our method to constraint satisfaction problems are discussed. [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]