A General Label Search to investigate classical graph search algorithms

Many graph search algorithms use a labeling of the vertices to compute an ordering of the vertices. We generalize this idea by devising a general vertex labeling algorithmic process called General Label Search (GLS), which uses a labeling structure which, when specified, defines specific algorithms.We characterize the vertex orderings computable by the basic types of searches in terms of properties of their associated labeling structures. We then consider performing graph searches in the complement without computing it, and provide characterizations for some searches, but show that for some searches such as the basic Depth-First Search, no algorithm of the GLS family can exactly find all the orderings of the complement. Finally, we present some implementations and complexity results of GLS on a graph and on its complement.     

A characterization of signed graphs with generalized perfect elimination orderings

An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.     

Pancyclic orderings of in-tournaments

An in-tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. In this paper, pancyclic orderings of a strong in-tournament D are investigated. This is a labeling, say x₁,x₂,…,x_n, of the vertex set of D such that D[{x₁,x₂,…,x_t}] is Hamiltonian for t=3,4,…,n. Moreover, we consider the related problem on weak pancyclic orderings, where the same holds for t4 and x₁ belongs to an arbitrary oriented 3-cycle. We present sharp lower bounds for the minimum indegree ensuring the existence of a pancyclic or a weak pancyclic ordering in strong in-tournaments.     

S/P images of upper triangular M-matrices

Preconditioning by approximate factorizations is widely used in iterative methods for solving linear systems such as those arising from the finite element formulation of many engineering problems. The influence of the ordering of the unknowns on their convergence behaviour has been the subject of recent investigations because of its particular relevance for the parallel implementation of these methods. Consistent orderings are attractive for parallel implementations and subclasses of these orderings have been shown to also enhance the convergence properties of the associated preconditioned iteration scheme. The present contribution is concerned with one such class of orderings, called S/P consistent orderings. More precisely, we review here their known properties and we propose a new definition which enlarges their scope of application. A device, called S/P image of an upper triangular M-matrix, provides a criterion for checking S/P consistency and a means to compute a relevant parameter, called maximal reduction ratio. All known properties of S/P consistent orderings are generalized to the new definition.     

Approximate factorizations with modified S/P consistently ordered M-factors

Preconditioned iterative methods are widely used to solve linear systems such as those arising from the finite element formulation of boundary value problems and approximate factorizations are widely used as preconditioners. The ordering of the unknowns is therefore an important issue because it has a strong influence on the convergence behaviour of the iteration method while it is also a decisive aspect for their parallel implementation. Consistent orderings are attractive for parallel implementations and it has been shown that some subclasses of these orderings also enhance the convergence behaviour of the associated iteration methods. This has in particular been shown for the so-called S/P consistent orderings. A wider definition of this class of orderings has recently been proposed and we investigate here how approximate factorizations should be implemented when using such more general orderings (still called S/P consistent) in order to keep their expected high convergence properties. A simple practical conclusion is suggested, supported by both theoretical and numerical arguments.     

Row-ordering schemes for sparse givens transformations. II. implicit graph model

A new graph model is presented to study the row annihilation and row ordering problems in the QR decomposition of sparse matrices using Givens rotations. The graph-theoretic results obtained can be used to derive good row orderings for certain column orderings, such as width-1 and width-2 nested dissection orderings. This model is different from the bipartite-graph model introduced in [6]. We refer to the new model as implicit because the rows are not represented explicitly by nodes, in contrast to the bipartite-graph model, where the rows are represented by nodes in a bipartite graph.     

A linear time algorithm to list the minimal separators of chordal graphs

Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph.     

Discovering Sparse Covariance Structures With the Isomap

Regularization of covariance matrices in high dimensions usually either is based on a known ordering of variables or ignores the ordering entirely. This article proposes a method for discovering meaningful orderings of variables based on their correlations using the Isomap, a nonlinear dimension reduction technique designed for manifold embeddings. These orderings are then used to construct a sparse covariance estimator, which is block-diagonal and/or banded. Finding an ordering to which banding can be applied is desirable because banded estimators have been shown to be consistent in high dimensions. We show that in situations where the variables do have such a structure, the Isomap does very well at discovering it, and the resulting regularized estimator performs better for covariance estimation than other regularization methods that ignore variable order, such as thresholding. We also propose a bootstrap approach to constructing the neighborhood graph used by the Isomap, and show it leads to better estimation. We illustrate our method on data on protein consumption, where the variables (food types) have a structure but it cannot be easily described a priori, and on a gene expression dataset. Supplementary materials are available online.     

Perfect elimination orderings for symmetric matrices

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.

     

双生成元$A_n$型拟遗传代数的拟遗传序

本文讨论双生成元$A_n$型代数的拟遗传序的性质,给出了该类代数的单模序是拟遗传序的充分必要条件,并利用组合技巧得出了该类代数拟遗传序的数目.     

Mathematical morphology on bipolar fuzzy sets: general algebraic framework

In many domains of information processing, bipolarity is a core feature to be considered: positive information represents what is possible or preferred, while negative information represents what is forbidden or surely false. If the information is moreover endowed with vagueness and imprecision, as is the case for instance in spatial information processing, then bipolar fuzzy sets constitute an appropriate knowledge representation framework. In this paper, we focus on mathematical morphology as a tool to handle such information and reason on it. Applying mathematical morphology to bipolar fuzzy sets requires defining an appropriate lattice. We extend previous work based on specific partial orderings to any partial ordering leading to a complete lattice. We address the case of algebraic operations and of operations based on a structuring element, and show that they have good properties for any partial ordering, and that they can be useful for processing in particular spatial information, but also other types of bipolar information such as preferences and constraints. Particular cases using Pareto and lexicographic orderings are illustrated. Operations derived from fuzzy bipolar erosion and dilation are proposed as well.     

Geometrical and Topological Properties of a Parameterized Binary Relation in Vector Optimization

In real linear spaces, partial orderings are usually generated by ordering cones. In many situations, however, such an ordering cone is too small with respect to the whole space. Therefore, in this paper, we extend the concept of ordering cones to a more general concept. For this purpose, we define a parameterized binary relation, based on a convex cone and a binary function. We investigate some geometrical and topological properties of this relation in detail.     

A criterion for the planarity of a graph

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244–271] has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion which, as well, is easily proved via Kuratowski's. The criterion is based on the observation that the imbedding of a graph in a plane imposes a cyclic ordering, say clockwise, on the edges incident with each vertex, and that these cyclic orderings are related.     

Linear combinations of heuristics for examination timetabling

Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In this paper, we explore this direction and introduce a new strategy of using linear combinations of heuristics for weighted graphs which model the timetabling problems under consideration. The weights of the heuristic combinations define specific roles that each simple heuristic contributes to the process of ordering vertices. We include specific explanations for the design of our strategy and present the experimental results on a set of benchmark real world examination timetabling problem instances. New best results for several instances have been obtained using this method when compared with other constructive methods applied to this benchmark dataset.     

On a Class of Lattice Ordered Inverse Semigroups

It is well known that the free group on a non-empty set can be totally ordered and, further, that each compatible latttice ordering on a free group is a total ordering. On the other hand, Saitô has shown that no non-trivial free inverse semigroup can be totally ordered. In this note we show, however, that every free inverse monoid admits compatible lattice orderings which are closely related to the total orderings on free groups.These orderings are natural in the sense that the imposed partial ordering on the idempotents coincides with the natural partial ordering. For this to happen in a lattice ordered inverse semigroup, the idempotents must form a distributive lattice. The method of construction of the lattice orderings on free inverse monoids can be applied to show that naturally lattice ordered inverse semigroups with a given distributive lattice E of idempotents can have arbitrary Green's relation structure. Analogous results hold for naturally -semilatticed inverse semigroups. In this case, there is no restriction on the semilattice E of idempotents.We also show that every compatible lattice ordering on the free monogenic inverse monoid is of the type considered here. This permits us to prove that there are precisely eight distinct compatible lattice orderings on this semigroup. They belong to two families, each of which contains four members, of conjuguate lattice orderings.     

General Variable Neighborhood Search for computing graph separators

Computing graph separators in networks has a wide range of real-world applications. For instance, in telecommunication networks, a separator determines the capacity and brittleness of the network. In the field of graph algorithms, the computation of balanced small-sized separators is very useful, especially for divide-and-conquer algorithms. In bioinformatics and computational biology, separators are required in grid graphs providing a simplified representation of proteins. This papers presents a new heuristic algorithm based on the Variable Neighborhood Search methodology for computing vertex separators. We compare our procedure with the state-of-the-art methods. Computational results show that our procedure obtains the optimum solution in all of the small and medium instances, and high-quality results in large instances.     

The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation

Summary Discretization of the Poisson equation on a rectangle by finite differences using the standard five-point stencil yields a linear system of algebraic equations, which can be solved rapidly by the cyclic reduction method. In this method a sequence of tridiagonal linear systems is solved. The matrices of these systems commute, and we investigate numerical aspects of their ordering. In particular, we present two new ordering schemes that avoid overflow and loss of accuracy due to underflow. These ordering schemes improve the numerical performance of the subroutine HWSCRT of FISHPAK. Our orderings are also applicable to the solution of Helmholtz's equation by cyclic reduction, and to related numerical schemes, such as FACR methods.Dedicated to the memory of Peter HenriciResearch supported in part by the National Science Foundation under Grant DMS-870416     

An indexed multivariate dispersion ordering based on the Hausdorff distance

A new multivariate dispersion ordering based on the Hausdorff distance between nonempty convex compact sets is proposed. This dispersion ordering depends on an index, whose purpose is to blur for each random vector the ball centered at its expected value, and with a radius equal to the index. So, on the basis of such an index, we consider a random set associated with each random vector and dispersion comparisons are established by means of the Hausdorff distance associated with the random sets. Different properties of the new dispersion ordering are stated as well as some characterization theorems. Possible relationships with other dispersion orderings are also studied. Finally, several examples are developed.     

The simplex dispersion ordering and its application to the evaluation of human corneal endothelia

A multivariate dispersion ordering based on random simplices is proposed in this paper. Given a R^d-valued random vector, we consider two random simplices determined by the convex hulls of two independent random samples of sizes d+1 of the vector. By means of the stochastic comparison of the Hausdorff distances between such simplices, a multivariate dispersion ordering is introduced. Main properties of the new ordering are studied. Relationships with other dispersion orderings are considered, placing emphasis on the univariate version. Some statistical tests for the new order are proposed. An application of such ordering to the clinical evaluation of human corneal endothelia is provided. Different analyses are included using an image database of human corneal endothelia.     

An Interactive Multiple Criteria Approach to Ranking Alternatives

In this paper we are concerned with ranking various orderings of a set of alternatives to a composite order as a multiple criteria problem. The orderings (called preference orderings) can be real preference orderings or any natural orderings. The objective is to find the most preferred order of the decision maker using the preference orderings as criteria.In principle, the problem can be formulated as a multiple objective linear programming problem using the model of Bowman and Colantoni and then solved with the interactive method proposed by Zionts and Wallenius. However, the fact that we are dealing with integer variables prohibits us from applying this approach as such. We discuss the problem formulation and propose a modified approach to that of Zionts and Wallenius for solving the problem.