Counting polycubes without the dimensionality curse

d-dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a d-D polycube of size n is a connected set of n cells of a d-dimensional hypercubic lattice, where connectivity is through (d−1)-dimensional faces of the cells. Computing A_d(n), the number of distinct d-dimensional polycubes of size n, is a long-standing elusive problem in discrete geometry. In a previous work we described the generalization from two to higher dimensions of a polyomino-counting algorithm of Redelmeier [D.H. Redelmeier, Counting polyominoes: Yet another attack, Discrete Math. 36 (1981) 191-203]. The main deficiency of the algorithm is that it keeps the entire set of cells that appear in any possible polycube in memory at all times. Thus, the amount of required memory grows exponentially with the dimension. In this paper we present an improved version of the same method, whose order of memory consumption is a (very low) polynomial in both n and d. We also describe how we parallelized the algorithm and ran it through the Internet on dozens of computers simultaneously.     

Network synchronizability analysis: The theory of subgraphs and complementary graphs

In this paper, subgraphs and complementary graphs are used to analyze network synchronizability. Some sharp and attainable bounds are derived for the eigenratio of the network structural matrix, which characterizes the network synchronizability, especially when the network’s corresponding graph has cycles, chains, bipartite graphs or product graphs as its subgraphs.     

Containment properties of product and power graphs

In this paper, we study containment properties of graphs in relation with the Cartesian product operation. These results can be used to derive embedding results for interconnection networks for parallel architectures.First, we show that the isomorphism of two Cartesian powers G^r and H^r implies the isomorphism of G and H, while G^r⊆H^r does not imply G⊆H, even for the special cases when G and H are prime, and when they are connected and have the same number of nodes at the same time.Then, we find a simple sufficient condition under which the containment of products implies the containment of the factors: if , where all graphs G_i are connected and no graph H_j has 4-cycles, then each G_i is a subgraph of a different graph H_j. Hence, if G is connected and H has no 4-cycles, then G^r⊆H^r implies G⊆H.Finally, we focus on the particular case of products of graphs with the linear array. We show that the fact that G×L_n⊆H×L_n does not imply that G⊆H even in the case when G and H are connected and have the same number of nodes. However, we find a sufficient condition under which G×L_n⊆H×L_n implies G⊆H.     

关于超欧拉图的一个注记

设G是无向无环的有限图 ,若G有一个生成子图是欧拉图 (Euler) ,则称G是超欧拉图 (Supereulerian) .本文不利用收缩方法 ,直接证明了 :当图G至多差一边有两棵边不相交的生成树时 ,G是超欧拉图或者G有割边 .     

Simplifying maximum flow computations: The effect of shrinking and good initial flows

Maximum flow problems occur in a wide range of applications. Although already well studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (1990) [12] for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm, flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods.     

Predicting link directions via a recursive subgraph-based ranking

Link directions are essential to the functionality of networks and their prediction is helpful toward a better knowledge of directed networks from incomplete real-world data. We study the problem of predicting the directions of some links by using the existence and directions of the rest of links. We propose a solution by first ranking nodes in a specific order and then predicting each link as stemming from a lower-ranked node and pointing toward a higher-ranked one. The proposed ranking method works recursively by utilizing local indicators on multiple scales, each corresponding to a subgraph extracted from the original network. Experiments on real networks show that the directions of a substantial fraction of links can be correctly recovered by our method, which outperforms either purely local or global methods.     

On the acyclic subgraph polytope

The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.     

An Efficient Sampling Algorithm for Network Motif Detection

We propose a sequential importance sampling strategy to estimate subgraph frequencies and detect network motifs. The method is developed by sampling subgraphs sequentially node by node using a carefully chosen proposal distribution. Viewing the subgraphs as rooted trees, we propose a recursive formula that approximates the number of subgraphs containing a particular node or set of nodes. The proposal used to sample nodes is proportional to this estimated number of subgraphs. The method generates subgraphs from a distribution close to uniform, and performs better than competing methods. We apply the method to four real-world networks and demonstrate outstanding performance in practical examples. Supplemental materials for the article are available online.     

The relationship between k-forcing and k-power domination

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of $k$-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, $k$-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of $k$-forcing and $k$-power domination, providing a new approach to analyze both processes. We give a relationship between the $k$-forcing and the $k$-power domination numbers of a graph that bounds one in terms of the other. We also obtain results using the contraction of subgraphs that allow the parallel computation of $k$-forcing and $k$-power dominating sets.