Network configuration verifiers can proactively reason about a network's correctness to prevent network outages. However, even recent efforts have proposed algorithms to "scale up" the verification to several thousand switches, these algorithms still cannot be used for networks with more than 10K switches or 1000M routes, which is common for large service providers. In this paper, instead of further scaling up the verification limited to a single server, we study how to "scale out" the verification using the resources of multiple servers. To achieve this, we propose S2, a distributed verifier for network configurations. S2 partitions the network model and distributes the verification tasks, i.e., control plane simulation and data plane verification, to run on multiple servers in parallel. Additionally, S2 uses prefix sharding during control plane simulation to further reduce the memory footprint on each server. We implement a prototype of S2 based on Batfish, the state-of-the-art network verifier. Based on real datacenter topologies of a large service provider and synthetic FatTree topologies, we show that S2 can verify networks with 10K routers and 1000M routes within 2 hours.

Computing the graph edit distance (GED) between graphs is the core operation in graph similarity search. Recent studies suggest that the existing index structures are ineffective in reducing the overall processing time of graph similarity search, and that directly verifying the GED between the query graph and every data graph in the database is still the best option. The state-of-the-art algorithm for GED verification is the recently proposed AStar-LSa. However, AStar-LSa may consume an extremely large amount of main memory or even run out-of-memory, when the graphs become larger and/or the GED threshold becomes larger. In this paper, we aim to improve the efficiency of GED verification and simultaneously lower the main memory consumption. To achieve that, we propose a new estimation for the lower bounds of partial mappings between graphs. We formally prove that our new lower bound is tighter than the one used in AStar-LSa. Moreover, we also propose efficient algorithms to compute the lower bounds, as well as optimization techniques to improve the efficiency. Empirical studies on real datasets demonstrate that our newly proposed algorithm AStar-BMao runs faster, and at the same time consumes much less main memory, than AStar-LSa.

Graph similarity search retrieves from a database all graphs whose edit distance (GED) to a query graph is within a threshold. As GED computation is NP-hard, the existing works adopt the filtering-and-verification paradigm to reduce the number of GED verifications, and they mainly focus on designing filtering techniques while using the now out-dated algorithm A*GED for verification. In this paper, we aim to speed up GED verification, which is orthogonal to the index structures used in the filtering phase. We propose a best-first search algorithm AStar+-LSa which improves A*GED by (1) reducing memory consumption, (2) tightening lower bound estimation, and (3) improving the time complexity for lower bound computation. We formally show that AStar+-LSa has a lower space and time complexity than A*GED. We further modify AStar+-LSa into a depth-first search algorithm to contrast these two search paradigms, and we extend our algorithms for exact GED computation. We conduct extensive empirical studies on real graph datasets, and show that our algorithm AStar+-LSa outperforms the state-of-the-art algorithms by several orders of magnitude for both GED verification and GED computation.

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C_1 and C_2 such that G-V(C_1 u̧p C_2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices.

Reliability analysis of an interconnection network is of great significance to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of a given interconnected network G with N processors, denoted by λh(G), is the minimum cardinality of set of faulty links, such that whose removal will disconnect the network with all its resulting components having at least h processors for h ≤ N/2. It gives a more refined quantitative analysis of indicators of the robustness of a multiprocessor system in the presence of failing links. The n-dimensional folded hypercube FQn, as one of potential interconnected networks, is a well-known variation of the hypercube structure with N = 2nprocessors. In this paper, the h-extra edge-connectivity of the network FQn, λh(FQn), is first investigated for each well-defined positive integer h ≤ N/2. We divide the interval 1 ≤ h ≤ N/2 into some subintervals and obtain some properties of λh(FQn) in these subintervals. Then, we deduce a recursive relation of λh(F Qn). Based on this recursion, an efficient O(log2(N)) algorithm is designed to totally determine the exact values and λh-optimality of λh(FQn) for each h ≤ N/2.

The paper studies two fundamental problems in graph analytics: computing Connected Components (CCs) and computing BiConnected Components (BCCs) of a graph. With the recent advent of Big Data, developing effcient distributed algorithms for computing CCs and BCCs of a big graph has received increasing interests. As with the existing research efforts, in this paper we focus on the Pregel programming model, while the techniques may be extended to other programming models including MapReduce and Spark. The state-of-the-art techniques for computing CCs and BCCs in Pregel incur O(m × #supersteps) total costs for both data communication and computation, where m is the number of edges in a graph and #supersteps is the number of supersteps. Since the network communication speed is usually much slower than the computation speed, communication costs are the dominant costs of the total running time in the existing techniques. In this paper, we propose a new paradigm based on graph decomposition to reduce the total communication costs from O(m×#supersteps) to O(m), for both computing CCs and computing BCCs. Moreover, the total computation costs of our techniques are smaller than that of the existing techniques in practice, though theoretically they are almost the same. Comprehensive empirical studies demonstrate that our approaches can outperform the existing techniques by one order of magnitude regarding the total running time.

Abstract A representation for area filling is described which allows shading of an area that may have both straight lines and circular arc edges and include holes within its boundaries. For efficiency an elimination algorithm which has a waiting line list and a currently active line list is adopted. For calculating intersections, a more time saving method is used. The algorithm and some practical examples are discussed. The main features of the algorithm are execution with high speed and less storage requirement. The program is written both in BASIC and FORTRAN 77 and could be executed on a microcomputer such as APPLE II, IBM‐P/C etc. The sample outputs shown in this paper are generated by the APPLE II with high efficiency.