Search

In the theory and applications of graphs, it is a basic problem to compute the numbers of independent sets and matchings of given sizes. Since the problem of computing the total number of independent sets and that of matchings of graphs is #P-complete, it is unlikely to give efficient algorithms to find the numbers of independent sets and matchings of given sizes. In this paper, for graphs with order n and treewidth at most p , we present two dynamic algorithms to compute the numbers of independent sets of all sizes with runtime O (2 p  ·  pn 3 ) and the numbers of matchings of all sizes with runtime O (2 2 p  ·  pn 3 ), respectively. By the algorithms presented in this paper, for graphs with small treewidths, the numbers of independent sets and matchings of all possible sizes can be computed efficiently. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a new method to establish a ranking of nodes in an urban network. In the original PageRank algorithm, a single PageRank vector is computed to determine the relative importance of Web pages, independent of any particular search query. We follow a similar reasoning, adapting the concept of PageRank vector to urban networks. We translate an urban network to graph theory language, where the nodes represent crossings or squares and the edges represent the connections between nodes. In this scenario, our main goal is to establish a ranking of importance of the different nodes in the graph. Unlike the PageRank model which only takes into account the connections between the Web pages, in our method we must consider other external factors to carry out the classification. These external factors may have some characteristics associated with the nodes and they are different according to the problem we are working. These characteristics are usually related to the presence of some facilities or endowments in the nodes of the network, like for example the presence of restaurants, bars, shopping centers, stores, and so on. A data matrix will collect the quantification of each of the characteristics studied for each node and will play an important role in the process of classification. Considering the influence of all these characteristics, we construct a matrix with some interesting algebraic features which allow us to compute an eigenvector associated to the dominant eigenvalue . This vector constitutes the solution to our problem of ranking the nodes of the network. The model is applied to a real example, in which we consider a part (the old town) of the city of Murcia (Spain). For this example, we apply the PageRank model, as well as the proposed model in this paper, in order to perform a comparative study of both models. This example clearly shows the importance of considering external factors to quantify the urban network nodes. [Copyright &y& Elsevier]

This paper aims to study the stochastic stabilization problem of complex networks without strong connectedness (CNSC). To deal with large-scale complex networks which are not strongly connected, a hierarchical method and a hierarchical algorithm are given, respectively. Meanwhile, we construct a logarithmic Lyapunov function for CNSC. Next, based on the theory of asymptotically autonomous systems, the Lyapunov method and the graph theory, the whole complex network can be stabilized by stabilizing a part of nodes. Then, stability criteria of CNSC are given, whose conditions reflect the relationship between dynamic properties and topology structure clearly. Furthermore, the theoretical results are applied to coupled oscillators on CNSC to ensure the stability. Finally, a numerical example is provided to illustrate the effectiveness and practicability of the results. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, for dealing with the portfolio model from stocks market, a new particle swarm optimization algorithm (NPSO) is presented, in which the optimal and sub-optimal positions of each particle are considered in the iteration process, and the crossover operation is used to avoid premature. It is demonstrated from optimization tests that NPSO outperforms existed PSO. Then NPSO is used to solve a discontinuous programming model, and four different optimal portfolio selections are displayed which are denoted by and , respectively. Finally, actual return rates of these portfolios are obtained, and it is analyzed from related graphs that and gain better results. [Copyright &y& Elsevier]

Abstract: Given a line graph of a graph , the problem of finding the minimum number of edges to add to to have a Hamiltonian path on is considered. This problem, related to different applications, is known to be NP-hard. This paper presents an algorithm to determine a lower bound for the Hamiltonian path completion number of a line graph. The algorithm is based on finding a collection of edge-disjoint trails dominating all the edges of the root graph G. The algorithm is tested by an extensive experimental study showing good performance suggesting its use as a building block of exact as well as heuristic solution approaches for the problem. [Copyright &y& Elsevier]

Abstract: Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. In this paper, we present efficient algorithms for solving these problems for Minesweeper graphs with bounded treewidth. Our algorithms turn out to be much better than those based directly on dynamic programming. The algorithms mostly use of algebraic operations on multivariate polynomials, so that one may use existing software to implement them easily. [Copyright &y& Elsevier]

Abstract: A characteristic feature of many relevant real life networks, like the WWW, Internet, transportation and communication networks, or even biological and social networks, is their clustering structure. We discuss in this paper a novel algorithm to identify cluster sets of densely interconnected nodes in a network. The algorithm is based on local information and therefore it is very fast with respect other proposed methods, while it keeps a similar performance in detecting the clusters. [ABSTRACT FROM AUTHOR]

Abstract: While the agility of networked organizational structures is important for organizational performance, studies on how to evaluate it remain scant, probably because the difficulty in measuring network evolution. In this conceptual paper, we propose two measures – network entropy and mutual information – to characterize the agility of networked organizational structure. Rooted in graph theory and information theory, these two measures capture network evolution in a comprehensive and parsimonious way. They indicate the uncertainty (or disorder) at the network level as well as the degree distribution at the individual level. We also propose an algorithm for applying them in the scenario of adding links to a network while holding the number of nodes fixed. Both simulated and real networks are used for demonstration. Implications and areas for future research are discussed in the end. [Copyright &y& Elsevier]

Abstract: Connectivity graphs are widely used in different branches of engineering, specially in ad hoc network analysis, decentralized control of unmanned air vehicles (UAV) and robot control. In large network simulations the extensive cost and the huge amount of memory required for performing the calculations is a major problem. Therefore methods should be developed that are fast and require less memory to determine the connectivity graph to expedite such calculations. In this paper we focus on approximate connectivity graphs for dynamic networks with moving agents. We use the velocity information of each agent to develop a fast algorithm to approximate the connectivity graph. Also we used mean degree distribution instead of degree distribution to investigate congestion/interference of network when approximate method is used. We introduced a modification factor for radio range R in Manhattan measure to increase the accuracy in a wide range of R. The results for two random distributions of agents based on Monte Carlo simulation are compared to the present real connectivity method to show the superiority of our approach. [Copyright &y& Elsevier]

Abstract: It is an important issue to design some performance indexes in order to measure the performance for a telecommunication network. Network analysis is an available approach to solve the performance problem for a real-life system. We construct a two-commodity stochastic-flow network with unreliable nodes (arcs and nodes all have several possible capacities and may fail) to model the telecommunication network. In which, all types of commodity are transmitted through the same network simultaneously and compete the capacities. This paper defines the system capacity as a 2-tuple vector, and then proposes a performance index, the probability that the upper bound of the system capacity equals a demand vector subject to the budget constraint. An upper boundary point is a vector representing the capacities of arcs and nodes, and is the maximal vector exactly meeting the demand vector. A simple algorithm based on minimal cuts (or named MC-based algorithm) is then presented to generate all upper boundary points in order to evaluate the performance index. The storage and computational time complexity of this algorithm are also analyzed. The performance evaluation for the multicommodity case can be extended easily. [Copyright &y& Elsevier]

Abstract: Fractal dimension is a suitable tool for analyzing the nonlinear behaviour and state of the dynamical systems. The algorithms of fractal dimension methods have weak ability to the estimation of complexity in the irregular graphs. In this paper we propose a new algorithm based on the size measure relationship (SMR) method, quantifying the dimensional behaviour of irregular rectifiable graphs with minimum time complexity. The evidence for the suitability (equality with the nature of dimension) of the algorithm is presented. [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: Financial options whose payoff depends critically on historical prices are called path-dependent options. Their prices are usually harder to calculate than options whose prices do not depend on past histories. Asian options are popular path-dependent derivatives, and it has been a long-standing problem to price them efficiently and accurately. No known exact pricing formulas are available to price them under the continuous-time Black–Scholes model. Although approximate pricing formulas exist, they lack accuracy guarantees. Asian options can be priced numerically on the lattice. A lattice divides the time to maturity into n equal-length time steps. The option price computed by the lattice converges to the option value under the Black–Scholes model as n →∞. Unfortunately, only subexponential-time algorithms are available if Asian options are to be priced on the lattice without approximations. Efficient approximation algorithms are available for the lattice. The fastest lattice algorithm published in the literature runs in O(n 3.5)-time, whereas for the related PDE method, the fastest one runs in O(n 3) time. This paper presents a new lattice algorithm that runs in O(n 2.5) time, the best in the literature for such methods. Our algorithm exploits the method of Lagrange multipliers to minimize the approximation error. Numerical results verify its accuracy and the excellent performance. [Copyright &y& Elsevier]

Abstract: In this paper, we study graphs that arise from certain sensory and communication limitations on the local interactions in multi-agent systems. In particular, we show that the set of graphs that can represent formations corresponds to a proper subset of all graphs and we denote such graphs as connectivity graphs. These graphs have a special structure that allows them to be composed from a small number of atomic generators using a certain kind of graph amalgamation. This structure moreover allows us to give connectivity graphs a topological characterization in terms of their simplicial complexes. Finally, we outline some applications of this topological characterization to the construction of decentralized algorithms. [Copyright &y& Elsevier]