Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning

Mathematical Programming - Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in...     

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.     

Genetic algorithms: Foundations and applications

Genetic algorithms are defined. Attention is directed to why they work: schemas and building blocks, implicit parallelism, and exponentially biased sampling of the better schema. Why they fail and how undesirable behavior can be overcome is discussed. Current genetic algorithm practice is summarized. Five successful applications are illustrated: image registration, AEGIS surveillance, network configuration, prisoner's dilemma, and gas pipeline control. Three classes of problems for which genetic algorithms are ill suited are illustrated: ordering problems, smooth optimization problems, and totally indecomposable problems.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

Efficient algorithms to compute all articulation points of a permutation graph

Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.     

Branch and bound algorithm with applications to robust stability

We discuss a branch and bound algorithm for global optimization of NP-hard problems related to robust stability. This includes computing the distance to instability of a system with uncertain parameters, computing the minimum stability degree of a system over a given set of uncertain parameters, and computing the worst case \(H_\infty \) norm over a given parameter range. The success of our method hinges (1) on the use of an efficient local optimization technique to compute lower bounds fast and reliably, (2) a method with reduced conservatism to compute upper bounds, and (3) the way these elements are favorably combined in the algorithm.     

An extremal problem for sets with applications to graph theory

Let X₁, …, X_n be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ? r_i and |B_ij| ? s_i for 1 ? i ? n, 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{ij}}\text{) = ?}$ for 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{il}}\text{) ≠ ?}$ for 1 ? j < l ? h. We prove that $\text{h?}\text{Π}\text{i=1}\text{n}\text{r}{}_{\mathrm{i}}\text{+s}{}_{\mathrm{i}}\text{r}{}_{\mathrm{i}}$. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).     

Median spheres: theory, algorithms, applications

A generalized hypersphere is either a hyperplane or a hypersphere, which consists of all points equidistant from a center. Geometrically, a weighted median hypersphere minimizes a weighted average of the distances from it to finitely many data points. As proved here, for each finite data set there exists at least one weighted median generalized hypersphere. Moreover, denote the sums of the weights of the data points inside by W ⁻, outside by W ⁺, and on the hypersphere by W ⁰. The present results show that each weighted median hypersphere is a weighted pseudo-halving hypersphere, in the sense that |W ⁻ − W ⁺| < W ⁰, and passes through at least two distinct data points. Combinatorically, a hypersphere is blocked if and only if it passes through data points in general position, in the sense that no other hypersphere passes through the same data points. A hypersphere is a halving hypersphere if and only if it is blocked, contains exactly k data points inside, confines exactly ℓ data points outside, and |k − ℓ| ≤ 1. In the plane, the present results also show that if a median circle is not a halving circle, then moving its center along a median between two data points on it until it passes through the next data point yields a halving circle. Relative to the center, if the direction cosines of the external and internal data points have the same mean and variance, then the median circle must be blocked, and stays so under sufficiently small perturbations of the data. Moreover, for every set of four points, at least one unweighted median circle is blocked. These results lend credence to a variant of a method used by archaeologists, and explain some findings from operations research.     

To teach or not to teach algorithms

Second, third, and fourth graders in 12 classes were individually interviewed to investigate the effects of teaching computational algorithms such as those of “carrying.” Some of the children had been encouraged to invent their own procedures and had not been taught any algorithms in grades 1 and 2, or in grades 1–3. Others had been taught the conventional algorithms prescribed by textbooks. The children were asked to solve multidigit addition and multiplication problems and to explain how they got their answers. It was found that those who had not been taught any algorithms produced significantly more correct answers. If children made errors, the incorrect answers of those who had not been taught any algorithms were much more reasonable than those found in the “Algorithms” classes. It was concluded that algorithms “unteach” place value and hinder children's development of number sense.     

Alternative gradient algorithms with applications to nonnegative matrix factorizations

Three nonnegative matrix factorization (NMF) algorithms are discussed and employed to three real-world applications. Based on the alternative gradient algorithm with the iteration steps being determined columnwisely without projection, and columnwisely and elementwisely with projections, three algorithms are developed respectively. Also, the computational costs and the convergence properties of the new algorithms are given. The numerical examples show the advantage of our algorithms over the multiplicative update algorithm proposed by Lee and Seung [11].     

Recentered Importance Sampling With Applications to Bayesian Model Validation

Since its introduction in the early 1990s, the idea of using importance sampling (IS) with Markov chain Monte Carlo (MCMC) has found many applications. This article examines problems associated with its application to repeated evaluation of related posterior distributions with a particular focus on Bayesian model validation. We demonstrate that, in certain applications, the curse of dimensionality can be reduced by a simple modification of IS. In addition to providing new theoretical insight into the behavior of the IS approximation in a wide class of models, our result facilitates the implementation of computationally intensive Bayesian model checks. We illustrate the simplicity, computational savings, and potential inferential advantages of the proposed approach through two substantive case studies, notably computation of Bayesian p-values for linear regression models and simulation-based model checking. Supplementary materials including the Appendix and the R code for Section are available online.     

Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph

For a graph G in read-only memory on n vertices and m edges and a write-only output buffer, we give two algorithms using only O(n) rewritable space. The first algorithm lists all minimal a−b separators of G with a polynomial delay of O(nm). The second lists all minimal vertex separators of G with a cumulative polynomial delay of O(n³m).One consequence is that the algorithms can list the minimal a−b separators (and minimal vertex separators) spending O(nm) time (respectively, O(n³m) time) per object output.     

Nonsmooth critical point theory and applications to the spectral graph theory

Existing critical point theories including metric and topological critical point theories are difficult to be applied directly to some concrete problems in particular polyhedral settings,because the notions of critical sets could be either very vague or too large.To overcome these difficulties,we develop the critical point theory for nonsmooth but Lipschitzian functions defined on convex polyhedrons.This yields natural extensions of classical results in the critical point theory,such as the Liusternik-Schnirelmann multiplicity theorem.More importantly,eigenvectors for some eigenvalue problems involving graph 1-Laplacian coincide with critical points of the corresponding functions on polytopes,which indicates that the critical point theory proposed in the present paper can be applied to study the nonlinear spectral graph theory.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

Several improved asymptotic normality criteria and their applications to graph polynomials

As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, this classical theorem exists some obvious shortcomings, for example, it requests all the roots of the corresponding generating function, which is impossible in general.Aiming to overcome this shortcoming in some extent, in this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail. Some relevant conjectures, proposed by Godsil (Combinatorica, 1981) and Wang et al. (J. Math. Anal. Appl., 2017), are generalized and verified as corollaries.     

When a line graph associated to annihilating-ideal graph of a lattice is planar or projective

Let (L,∧, ∨) be a finite lattice with a least element 0. AG(L) is an annihilating-ideal graph of L in which the vertex set is the set of all nontrivial ideals of L, and two distinct vertices I and J are adjacent if and only if I ∧ J = 0. We completely characterize all finite lattices L whose line graph associated to an annihilating-ideal graph, denoted by L(AG(L)), is a planar or projective graph.