A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph

We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass.     

Efficient enumeration of words in regular languages

The cross-section enumeration problem is to list all words of length n$n$ in a regular language L$L$ in lexicographical order. The enumeration problem is to list the first m$m$ words in L$L$ according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in n+t$n+t$, where t$t$ is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable.     

Landmark transfer with minimal graph

We present an efficient and robust algorithm for the landmark transfer on 3D meshes that are approximately isometric. Given one or more custom landmarks placed by the user on a source mesh, our method efficiently computes corresponding landmarks on a family of target meshes. The technique is useful when a user is interested in characterization and reuse of application-specific landmarks on meshes of similar shape (for example, meshes coming from the same class of objects). Consequently, across a set of multiple meshes consistency is assured among landmarks, regardless of landmark geometric distinctiveness. The main advantage of our method over existing approaches is its low computation time. Differently from existing non-rigid registration techniques, our method detects and uses a minimum number of geometric features that are necessary to accurately locate the user-defined landmarks and avoids performing unnecessary full registration. In addition, unlike previous techniques that assume strict consistency with respect to geodesic distances, we adopt histograms of geodesic distance to define feature point coordinates, in order to handle the deviation of isometric deformation. This allows us to accurately locate the landmarks with only a small number of feature points in proximity, from which we build what we call a minimal graph. We demonstrate and evaluate the quality of transfer by our algorithm on a number of Tosca data sets.     

Planar articulated mechanism design by graph theoretical enumeration

This paper deals with design of articulated mechanisms using a truss-based ground-structure representation. By applying a graph theoretical enumeration approach we can perform an exhaustive analysis of all possible topologies for a test example for which we seek a symmetric mechanism. This guarantees that one can identify the global optimum solution. The result underlines the importance of mechanism topology and gives insight into the issues specific to articulated mechanism designs compared to compliant mechanism designs.     

Generation of all possible trees of a graph in independent groups

A special graph, the PS graph, is introduced and an algorithm is developed to generate all trees of such graphs. It is proved that for any given graph, $\text{G}$ there exists certain number of PS graphs, obtained from $\text{G}$, such that the collection of all trees of all such PS graph span all trees of $\text{G}$ with no duplication. In addition to a number of properties of PS graphs indicated, the procedure seems very useful for topological analysis and design of networks, or any other types of systems that can be represented by a linear graph.     

Enumeration of all minimum feedback edge sets in a directed graph

The purpose of the present paper is to propose an efficient algorithm to enumerate all the minimum feedback edge sets of a given directed graph. The algorithm has been developed in two distinct phases, i.e. all the directed circuits of the given graph are generated at the first phase and then the minimum feedback edge sets are determined from the information of the directed circuits. The proposed algorithm offers easy programmability on a digital computer, and it seems economic in terms of computation time and required storage space.     

A parallel algorithm for the enumeration of the spanning trees of a graph

As is well known, the strategy of divide-and-conquer is widely used in problem solving. The method of partitioning is also a fundamental strategy for the design of a parallel algorithm. The problem of enumerating the spanning trees of a graph arises in several contexts such as computer-aided design and computer networks. A parallel algorithm for solving the problem is presented in this paper. It is based on the principle of the inclusion and exclusion of sets, and not directly based on the partitioning of the graph itself. The results of the preliminary experiments on a MIMD system appear promising.     

Motorcycle graph enumeration from quadrilateral meshes for reverse engineering

Recently proposed quad-meshing techniques allow the generation of high-quality semi-regular quadrilateral meshes. This paper outlines the generation of quadrilateral segments using such meshes. Quadrilateral segments are advantageous in reverse engineering because they do not require surface trimming or surface parameterization. The motorcycle graph algorithm of Eppstein et al. produces the motorcycle graph of a given quadrilateral mesh consisting of quadrilateral segments. These graphs are preferable to base complexes, because the mesh can be represented with a smaller number of segments, as T-joints (where the intersection of two neighboring segments does not involve the whole edge or the vertex) are allowed in quadrilateral segmentation.The proposed approach in this study enumerates all motorcycle graphs of a given quadrilateral mesh and optimum graph for reverse engineering is then selected. Due to the high computational cost of enumerating all these graphs, the mesh is cut into several sub-meshes whose motorcycle graphs are enumerated separately. The optimum graph is then selected based on a cost function that produces low values for graphs whose edges trace a large number of highly curved regions in the model. By applying several successive enumeration steps for each sub-mesh, a motorcycle graph for the given mesh is found. We also outline a method for the extraction of feature curves (sets of highly curved edges) and their integration into the proposed algorithm. Quadrilateral segments generated using the proposed techniques are validated by B-spline surfaces.     

Computer construction and enumeration of all topologies and all hyperconnected topologies on finite sets

In [1] the present authors described an algorithm to construct and enumerate specific topologies on a finite set X _n of n points that is the strictly weaker topologies on X _n than a given topology each of which is not contained in any excluding point topology on X _n . In this paper we describe an algorithm to construct and enumerate all topologies and all hyperconnected topologies on X _n . The topologies on X _n which are weaker than a given topology on X _n will be constructed and enumerated. The algorithm is written in Fortran 77 and implemented on an Pentium 400 system.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and “unicycular graphs.” Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and unicycular graphs. Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.Part of this work was done while the first author was at the University of Illinois, Urbana-Champaign, the second author was at Carnegie-Mellon University, and the third author was at the Hebrew University and the Courant Institute of Mathematical Sciences, New York University. A preliminary version of this work was presented at the 1986 International Conference on Parallel Processing.     

Efficient parallel graph trimming by arc-consistency

The Journal of Supercomputing - Given a large data graph, trimming techniques can reduce the search space by removing vertices without outgoing edges. One application is to speed up the parallel...     

Parametrization of all minimal square spectral factors

Two different parametrizations of minimal square spectral factors are given. These parametrizations extend recent results by Picci and Pinzoni since they characterize spectral factors without specification on the zero or pole structure.     

The set of all minimal partial realizations

This paper is concerned with the uniqueness of minimal partial realizations. Earlier papers are typically concerned with the problem of the existence and the determination of a matrix triple(tilde{A},tilde{B},tilde{C})which is a minimal partial realization of a sequence{Y_{1},...,Y_{m}}of Markov parameters. In this paper a parameterized realization(A(y),B, C)(yis a parameter vector) is defined which characterizes the set of all minimal partial realizations of the sequence{ Y_{1},. . . , Y_{m}}. An example is provided and the utility of the parameterization is discussed.     

Efficient source enumeration for accurate direction-of-arrival estimation in threshold region

Estimation of the number of signals impinging on an array of sensors, also known as source enumeration, is usually required prior to direction-of-arrival (DOA) estimation. In challenging scenarios such as the presence of closely-spaced sources and/or high level of noise, using the true source number for nonlinear parameter estimation leads to the threshold effect which is characterized by an abnormally large mean square error (MSE). In cases that sources have distinct powers and/or are closely spaced, the error distribution among parameter estimates of different sources is unbalanced. In other words, some estimates have small errors while others may be quite inaccurate with large errors. In practice, we will be only interested in the former and have no concern on the latter. To formulate this idea, the concept of effective source number (ESN) is proposed in the context of joint source enumeration and DOA estimation. The ESN refers to the actual number of sources that are visible at a given noise level by a parameter estimator. Given the numbers of sensors and snapshots, number of sources, source parameters and noise level, a Monte Carlo method is designed to determine the ESN, which is the maximum number of available accurate estimates. The ESN has a theoretical value in that it is useful for judging what makes a good source enumerator in the threshold region and can be employed as a performance benchmark of various source enumerators. Since the number of sources is often unknown, its estimate by a source enumerator is used for DOA estimation. In an effort to automatically remove inaccurate estimates while keeping as many accurate estimates as possible, we define the matched source number (MSN) as the one which in conjunction with a parameter estimator results in the smallest MSE of the parameter estimates. We also heuristically devise a detection scheme that attains the MSN for ESPRIT based on the combination of state-of-the-art source enumerators.