A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

A fast algorithm for computing parametric rational functions

An algorithm for fast computation of a class of parametric rational functions whose coefficients are assumed to be affine functions of some underlying parameters is described. The algorithm has been implemented in Microsoft Quick BASIC 4.0. Execution times are minimal     

A linear expected-time algorithm for computing planar relative neighbourhood graphs

A new algorithm for computing the relative neighbourhood graph (RNG) of a planar point set is given. The expected running time of the algorithm is linear for a point set in a unit square when the points have been generated by a homogeneous planar Poisson point process. The worst-case running time is quadratic on the number of the points. The algorithm proceeds in two steps. First, a supergraph of the RNG is constructed with the aid of a cell organization of the points. Here, a point is connected by an edge to some of its nearest neighbours in eight regions around the point. The nearest region neighbours are chosen in a special way to minimize the costs. Second, extra edges are pruned from the graph by a simple scan.     

A fast algorithm for computing a histogram on reconfigurable mesh

The reconfigurable mesh captures salient features from a variety of sources, including the content addressable array parallel processor, the CHiP, the polymorphic-torus network and the bus automaton. It consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns between the processors. In this paper, we present a fast algorithm for computing the histogram of an N×N image with h grey levels in O(min{√h+log*(N/h),N}) time on an N×N reconfigurable mesh assuming each PE has a constant amount of local memory. This algorithm runs on the PARBUS and MRN/LRN models. In addition, histogram modification can be performed in O(√h) time on the same model. A variant of out algorithm runs in O(min{√h+log log(N/h),N}) time on an N×N RMESH in which each PE has constant storage. This result improves the known time and memory bounds for histogramming on the RMESH model     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

A fast algorithm for computing minimum routing cost spanning trees

Communication networks have been developed based on two networking approaches: bridging and routing. The convergence to an all-Ethernet paradigm in Personal and Local Area Networks and the increasing heterogeneity found in these networks emphasizes the current and future applicability of bridging. When bridging is used, a single active spanning tree needs to be defined. A Minimum Routing Cost Tree is known to be the optimal spanning tree if the probability of communication between any pair of network nodes is the same. Given that its computation is a NP-hard problem, approximation algorithms have been proposed.We propose a new approximation Minimum Routing Cost Tree algorithm. Our algorithm has time complexity lower than the fastest known approximation algorithm and provides a spanning tree with the same routing cost in practice. In addition, it represents a better solution than the current spanning tree algorithm used in bridged networks.     

A new exact maximum clique algorithm for large and massive sparse graphs

This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.     

A simple and fast algorithm for computing exponentials of power series

As was initially shown by Brent, exponentials of truncated power series can be computed using a constant number of polynomial multiplications. This note gives a relatively simple algorithm with a low constant factor.     

An efficient algorithm for computing permanental polynomials of graphs

An efficient numerical method for computing permanental polynomials of graphs is proposed. It adapts multi-entry expansion of FFT, and is parallel in nature. It is applied to fullerene-type graphs, and works for C₅₆, while the largest fullerene computed before is C₄₀. Extensive numerical computations show that the algorithm is fast and stable.     

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing an MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.     

A fast algorithm for computing integrals in function spaces: Financial applications

The paper describes a fast and general numerical algorithm for computing path integrals in function spaces. Efficiency is ensured by use of FFT-based procedures as the primary element of the algorithm. The total number of operations required by the algorithm can be shown to be proportional to the total number of discretization nodes. A number of financial applications of the algorithm are considered, including pricing European and American style interest rate options, path dependent options, and index amortization swaps.     

快速稀疏表示分类的人脸识别算法

经典的稀疏表示分类（Sparse Representation for Classification,SRC）算法是一种基于[L1]范数最小化问题,它在很多应用场合都能取得很好的分类效果,是目前备受关注的一类识别算法。然而,传统的SRC算法在求解[L1]范数最小化问题时,往往计算效率比较低。为有效解决这个问题,提出了一种快速有效的分类算法,它利用坐标下降方法来实现SRC算法。该方法既可以显著地提高计算效率,又可取得较好的分类结果。在不同人脸库上的实验表明,所提的算法具有良好的应用前景。     

A fast algorithm for computing least-squares cross-validations for nonparametric conditional kernel density functions

Nonparametric conditional density functions are widely used in applied econometric and statistical modelling because they provide enriched information summaries of the relationships between dependent and independent variables. Although least-squares cross-validation is considered to be the best criterion for bandwidth selection of the kernel estimator of the conditional density, the number of computations required for this procedure grows exponentially as the number of observations increases. A fast algorithm is proposed to reduce this computational cost, and its accuracy and efficiency are verified via numerical experiments. A practical application is also presented to demonstrate the algorithm’s potential usefulness.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

同构计算环境中DAG任务图的调度算法

在并行多处理机系统中,任务调度算法是保证整个系统性能的关键.通常用有向无环图(DAG)表示任务间的依赖关系.将粒子群算法应用于组合优化领域,构造了求解任务调度问题的离散粒子群算法.算法采用基于分组的思想对粒子进行直接编码,借鉴遗传算法的思想,将粒子个体最优及全局最优解分别采用交又操作作用到当前粒子位置上,使粒子不断向最优位置逼近;同时在每次迭代过程中引入变异操作以提高粒子群体多样性.实验结果表明,算法在不同规模的任务调度问题中均取得了良好的效果.     

A low-latency computing framework for time-evolving graphs

The Journal of Supercomputing - The demand to deliver fast responses in processing time-evolving graphs is higher than ever before in a large number of big data applications. This problem promotes...     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.