A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

混合图在无向图割集生成中的应用

为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集.在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度.理论分析结果和实验比较结果均表明改进算法明显比现有算法高效.     

A factorization algorithm to compute Pfaffians

We describe an explicit algorithm to factorize an even antisymmetric N² matrix into triangular and trivial factors. The construction resembles the Crout algorithm for LU factorization. It allows for a straight forward computation of Pfaffians (including their signs) at the cost of N³/3 flops.     

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.     

A greedy approach to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 358] and hereby obtain a very simple exact algorithm of complexity , being as fast as the first algorithm proposed for this problem [A polynomial time algorithm for minimum cycle basis in directed graphs, Kurt Mehlhorn's List of Publications, 185, MPI, Saarbrücken, 2004, http://www.mpi-sb.mpg.de/~mehlhorn/ftp/DirCycleBasis.ps; Proc. STACS 2005, submitted for publication]. Moreover, the speed-up of Golynski and Horton [A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in: M. Penttonen, E. Meineche Schmidt (Eds.), SWAT 2002, Lecture Notes in Comput. Sci., vol. 2368, Springer, Berlin, 2002, pp. 200-209] applies to this problem, providing an exact algorithm of complexity , in particular . Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.     

A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

Efficiently searching a graph by a smell-oriented vertex process

Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the Vertex-Ant-Walk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O(nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a trade-off between random and self-avoiding walks, as it dictates a lower priority for already-visited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between them; (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process. This revised version was published online in June 2006 with corrections to the Cover Date.     

A DSL for graph parallel programming with vertex subsets

The Journal of Supercomputing - The vertex-centric (VC) computation model has emerged as a promising approach for easy parallel programming and massive parallel execution for big graph processing....     

A new parallel algorithm for vertex priorities of data flow acyclic digraphs

Data flow acyclic directed graphs (digraph) are widely used to describe the data dependency of mesh-based scientific computing. The parallel execution of such digraphs can approximately depict the flowchart of parallel computing. During the period of parallel execution, vertex priorities are key performance factors. This paper firstly takes the distributed digraph and its resource-constrained parallel scheduling as the vertex priorities model, and then presents a new parallel algorithm for the solution of vertex priorities using the well-known technique of forward–backward iterations. Especially, in each iteration, a more efficient vertex ranking strategy is proposed. In the case of simple digraphs, both theoretical analysis and benchmarks show that the vertex priorities produced by such an algorithm will make the digraph scheduling time converge non-increasingly with the number of iterations. In other cases of non-simple digraphs, benchmarks also show that the new algorithm is superior to many traditional approaches. Embedding the new algorithm into the heuristic framework for the parallel sweeping solution of neutron transport applications, the new vertex priorities improve the performance by 20 % or so while the number of processors scales up from 32 to 2048.     

A recursive algorithm to compute the baseline drift in recorded biological signals

Baseline estimation and removal is one of the main problems to overcome in order to obtain a correct interpretation of recorded biological signals. The method described in this paper is based on a new application of recursive estimation of a smoothing spline, selected to model the unknown baseline. Its advantages over conventional methods derive from these characteristics: it is parametric and recursive, it works in the time domain, and the same software can be used in different applications, since no a priori frequency knowledge is needed. In the example, the method is applied to ECG recordings and a spectral analysis is thereby shown.     

A fast algorithm to compute irreducible and primitive polynomials in finite fields

In this paper we present a method to computeall the irreducible and primitive polynomials of degreem over the finite fieldGF(q). Our method finds each new irreducible or primitive polynomial with a complexity ofO(m) arithmetic operations inGF(q). The best previously known methods [3], [10] use the Berlekamp-Massey algorithm [7] and they have a complexityO(m ²). We reach mis improvement taking into account a systolic implementation [2] of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm.This work was supported in part by Spanish Grant CICYT TIC91-0472.     

A parallel algorithm to construct a dominance graph on nonoverlapping rectangles

A parallel algorithm to generate the dominance graph on a collection of nonoverlapping iso-oriented rectangles is presented. This graph arises from the constraint graph commonly used in compaction algorithms for VLSI circuits. The dominance graph expresses the notion of aboveness on a collection of nonoverlapping rectangles: it is the directed graph which contains an edge from a rectangleb to rectanglec iffc is immediately aboveb. The algorithm is based on the divide and conquer paradigm; in the EREW PRAM model, it has time complexityO(log² n), usingn/logn processors. Its processor-time product isO(nlogn), which is optimal.     

A new linear time algorithm to compute the genomic distance via the double cut and join distance

The genomic distance problem in the Hannenhalli–Pevzner (HP) theory is the following: Given two genomes whose chromosomes are linear, calculate the minimum number of translocations, fusions, fissions and inversions that transform one genome into the other. This paper presents a new distance formula based on a simple tree structure that captures all the delicate features of this problem in a unifying way, and a linear time algorithm for computing this distance.     

A neural-network algorithm for a graph layout problem

We present a neural-network algorithm for minimizing edge crossings in drawings of nonplanar graphs. This is an important subproblem encountered in graph layout. The algorithm finds either the minimum number of crossings or an approximation thereof and also provides a linear embedding realizing the number of crossings found. The parallel time complexity of the algorithm is O(1) for a neural network with n(2) processing elements, where n is the number of vertices of the graph. We present results from testing a sequential simulator of the algorithm on a set of nonplanar graphs and compare its performance with the heuristic of Nicholson.     

Determining the feature relevance for non-classically described objects and a new algorithm to compute typical fuzzy testors

In this paper we introduce an algorithm for computing all the typical fuzzy testors of a training matrix with non-classically described objects in Goldman's approach. We also introduce a new expression for determining the feature relevance in crisp and fuzzy environments.     

On the feedback vertex set problem for a planar graph

An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gauß-Seidel smoothers in multi-grid methods.