Frequent Subgraph Mining (FSM) is the process of identifying common subgraph patterns that occur over a certain threshold. The NP-hardness of FSM makes it a complex and time-consuming task. FSM is generally solved in 2 steps, 1). Generation step: determining the possible patterns that can be frequent and 2). Metric step: determining if the pattern is frequent. In the literature, the generation step is usually solved by vertex or edge extension methods. These methods produce a lot of redundant candidate patterns which must be removed, and hence increasing the latency. To address these challenges, the paper introduces a vertex based merging method which reduces the redundancies, and introduces effective pruning mechanisms. Moreover, the existing metrics to determine if a pattern is frequent or not, either is highly accurate while demanding significant computational time (Maximum Independent Set (MIS)) or overestimates the pattern count while taking less time (Minimum Node Image (MNI)). Thus, the paper introduces ''Maximal Independent Set (mIS)'' metric, which minimizes latency while obtaining accuracy close to MIS, which is controlled by a pattern overlap parameter (łambda).Through extensive experimentation, our proposed method achieves an average of 10.58× speedup when compared to GraMi and an average of 3× speedup when compared to T-FSM.

Abstract We consider the network analytics problem of comparing two distance metrics on the same set of n entities. The classical solution to this problem is the Mantel test, which uses permutation testing to accept or reject the null hypothesis that there is “no relationship between the two metrics.” Its computational complexity is n2 times the number of permutations (based on a user supplied parameter). This work makes two contributions: (1) DIMECOSTP, a more efficient hypothesis test based on uniform random spanning trees whose complexity is n times the number of permutations. (2) DIMECOSTCC, which uses the correlation coefficient between the two sets of edge weights in a random spanning tree as an indication of the strength of the relationship between the two distance metrics. Both methods utilize sound statistical principles. Experimental results confirm the efficacy of our methods.

We describe a competition-based group project that has been in use in the Algorithms course at our institution each semester since 2012. The class is given an NP-hard optimization problem; each student group is asked to create a heuristic algorithm for the problem. The heuristic is run on a set of inputs (with each group supplying one input) and groups are ranked based on their aggregate performance within a specified time period. This paper describes our experience with this approach, including challenges, and our recent efforts to address these through a web application used to facilitate the competition.

Despite their illegality, untethered free‐floating naval mines are increasingly employed as part of maritime area‐denial operations. By ignoring international treaties, these mines require less effort to acquire and deploy, and result in a far more dynamic‐threat environment. In order to assist commanders during breach operation planning, we develop several algorithms that generate a minimum‐risk journey through a field of drifting mines. Using Voronoi graphs to capture a series of static snapshots of the operational area, we present a practical methodology for building a fully connected time‐varying graph . Vertices are defined as specific times and locations, and edges ℰ define the continuous movement of a ship with simple parametric equations. The length, acceleration and risk of each edge is calculated and employed by a threat‐additive A* search to quickly find a plausible, minimum‐risk journey through a given minefield within a specific time frame. Using real‐world data for a modern‐day port and minefields of variable density, we find navigable paths that incur acceptable risk in less than 2 minutes on average. We also introduce several methods for reducing the size of and the time required for its generation.

Graphlet counting is a methodology for detecting local structural properties of large graphs that has been in use for over a decade. Despite tremendous effort in optimizing its performance, even 3- and 4-node graphlet counting routines may run for hours or days on highly optimized systems. In this paper, we describe how a synergistic combination of approximate computing with parallel computing can result in multiplicative performance improvements in graphlet counting runtimes with minimal and controllable loss of accuracy. Specifically, we describe two novel techniques, multi-phased sampling for statistical accuracy guarantees and cost-aware sampling to further improve performance on multi-machine runs, which reduce the query time on large graphs from tens of hours to several minutes or seconds with only <;1% relative error.

The matching problem in bipartite graphs is the basis for many applications that have become especially prominent with the advent of online markets that connect two entities (e.g., job-seekers and employers). Its algorithmic basis is the max-flow problem in networks, a topic that is often covered in introductory algorithms texts and courses.

This paper considers the general problem of relocating modules to convert infeasible constrained floorplanner inputs into feasible ones. This is accomplished by placing modules in locations that attempt to minimize the standard deviation of module densities. Efficient geometric algorithms are developed and shown to be successful in obtaining feasible inputs. Experimental results examine the tradeoffs between achieving a good redistribution of density on one hand and minimizing the increase in wire length and the displacement of modules on the other.

This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" (Kahng, 2000). Specifically, the constrained modern floorplanning problem (CMFP) is suitable when die-size is fixed, modules are permitted to have rectilinear shapes and, in addition, the approximate relative positions of the modules are known. This formulation is particularly useful in two scenarios: 1) assisting an expert floorplan architect in a semiautomated floorplan methodology and 2) in incremental floorplanning. CMFP is shown to be negative-positive hard. An algorithm based on a max-flow network formulation quickly identifies input constraints that are impossible to meet, thus permitting the floorplan architect to modify these constraints. Three algorithms [Breadth First Search (BFS), Improved BFS (IBFS), Compromise BFS (CBFS)] based on using BFS numbers to assign costs in a min-cost max-flow network formulation are presented. Experiments on standard benchmarks demonstrate that IBFS is fast and effective in practice.

Network wide broadcast is a fundamental operation in mobile ad hoc networks (MANETs). Several broadcast protocols have been proposed in the literature that improves on simple flooding by reducing the probability that a receiving node retransmits a packet. We propose analytical models to estimate these probabilities for three broadcast protocols. Our simulations show that these analytical models, which were derived under some simplifying assumptions, predict retransmission probabilities for static and mobile networks quite accurately when only the network layer is considered.

This paper discusses the computation of optimal coverage paths in an ad-hoc network consisting of n sensors. Improved algorithms, with a preprocessing time of O(n log n), to compute a maximum breach/support path P in optimal (|P|) time or the maximum breach/support value in O(1) time are presented. Algorithms for computing a shortest path that has maximum breach/support are also provided. Experimental results for breach paths show that the shortest path length is on the average 30% less and is not much worse that the ideal straight line path. For applications that require redundancy (i.e., detection by multiple sensors), a generalization of Voronoi diagrams allows us to compute maximum breach paths where breach is defined as the distance to the kth nearest sensor in the field. Extensive experimental results are provided.

This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" [1]. Specically, the constrained modern floorplanning problem (CMFP) is suitable when die-size is fixed, modules are permitted to have rectilinear shapes, and, in addition, the approximate relative positions of the modules are known. This formulation is particularly useful in two scenarios: (1) assisting an expert floorplan architect in a semi-automated floorplan methodology and (2) in incremental floorplanning. CMFP is shown to be NP hard. An algorithm based on a max-flow network formulation quickly identifies input constraints that are impossible to meet, thus permitting the floorplan architect to modify these constraints. Three algorithms (BFS, IBFS, CBFS) based on using BFS numbers to assign costs in a min-cost max-flow network formulation are presented. Experiments on standard benchmarks demonstrate that BFS and IBFS are fast and obtain zero whitespace floorplans.

A productivity-driven methodology for incremental floorplanning is described and the constrained polygon transformation problem , a key step of this methodology, is formulated. The input to the problem consists of a floorplan computed using area estimates and the actual area required for each subcircuit of the floorplan. Informally, the objective is to change the areas of the modules without drastically changing their shapes or locations. We show that the constrained polygon transformation problem is NP-hard and present several fast algorithms that produce results within a few percent of a theoretical lower bound on several floorplans.

This paper presents three minimum-area floorplanning algorithms that use flexible arbitrary rectilinear shapes for the standard cell regions in MBC design. The first algorithm (pure HCST) introduces a grid traversal technique which guarantees a minimum-area floorplan. The second algorithm (Hybrid-BF) uses a combination of HCST and Breadth First (BF) traversals to give a practical solution that approximately places flexible blocks at specified locations calledseeds. The third algorithm (Hybrid-MBF) improves on the shapes of the flexible blocks generated by Hybrid-BF by using a combination of HCST and a Modified Breadth First (MBF) traversal. All three algorithms are polynomial in the number of grid squares. Optimized implementations of Hybrid-BF and Hybrid-MBF required less than two seconds on a SUN SPARCstation 10.

Corner stitching is the underlying data structure that is used to represent rectangular objects in interactive VLSI layout editing systems such as Magic and Tailor. In this paper we develop efficient algorithms for basic corner stitching operations under the message-passing paradigm. These algorithms were implemented using C and PVM on a distributed network composed of SUN workstations. Experimental results show that significant speed-ups were obtained. © 1998 John Wiley & Sons, Ltd.

This paper proposes a technique for estimating the storage requirements of the Rectangular Corner Stitching (RCS) data structure [Ousterhout 1984] and the L-shaped Corner Stitching (LCS) data structure [Mehta and Blust 1997] on a given circuit by studying its (the circuit's) geometric properties. This provides a method for estimating the storage requirements of a circuit without having to implement the corner stitching data structure, which is a tedious and time-consuming task. This technique can also be used to estimate the amount of space saved by employing the LCS data structure over the RCS data structure on a given circuit.

This paper extends the corner-stitching data structure proposed by Ousterhout (1984) for manipulating rectangular objects in very large scale integration (VLSI) layouts to L-shaped objects. This provides additional flexibility in the design of very large scale integration (VLSI) circuits. Our technique is fundamentally different from Ousterhout's and other extensions to the corner stitching data structure in that it modifies the underlying topology of the data structure. This gives rise to differences in the implementation of operations on the data structure. Our data structure is guaranteed to require less memory than the original data structure. Experiments show that our data structure required about 15%-17% less memory than the original data structure on VLSI layouts but was slower by a factor of two to eight. Extensions of corner stitching to T- and Z-shaped tiles are also described.

We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; i.e., our algorithms decompose a simple polygon into non-overlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes an optimal configuration for a wide variety of optimization functions, while the other computes a minimum configuration of rectangles and L-shapes. Both run in O(n+h log h) time, where n is the number of vertices in the polygon and h is the number of H-pairs. Experimental results on VLSI data demonstrate the gains in performance for corner stitching obtained by using our algorithms instead of traditional rectangular partitioning algorithms.

This paper identifies important objectives that an MBC floorplanner using flexible, arbitrary rectilinear shapes for standard cell regions should achieve including area minimization, proximity, and connectivity. It then presents an algorithm that guarantees area minimization and connectivity and gives good results with respect to proximity.

We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; that is, our algorithms decompose a simple polygon into a set of nonoverlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes and optimal configuration for a wide variety of optimization functions, whereas the other computes a minimum configuration of rectangles and L-shapes. Both algorithms run in O ( n + h log h time, where n is the number of vertices in the polygon and h is the number of H-pairs. Because for VLSI data h is small, in practice these algorithms are linear in n . Experimental results on actual VLSI data compare our algorithms and demonstrate the gains in performance for corner stitching (as measured by different objective functions) obtained by using them instead of more traditional rectangular partitioning algorithms.

This paper proposes a technique for estimating the storage requirements of the Rectangular Corner Stitching (RCS) data structure and the L-Shaped Corner Stitching (LCS) date structure on a given circuit by studying its (the circuit's) geometric properties. This provides a method for estimating the storage requirements of a circuit without having to implement the Corner Stitching data structure, which is a tedious and time-consuming task. This technique can also be used to estimate the amount of space saved by employing the LCS data structure over the RCS data structure on a given circuit.>

Strings are used to represent a variety of objects such as DNA sequences, text, and numerical sequences. A model for a system for the visualization and analysis of strings was proposed by D. Mehta and S. Sahni (1992). The problem of display conflicts that arise in this model was identified and methods to overcome it were suggested. These methods require the computation of display conflicts. We present efficient algorithms to compute display conflicts.>

The corner-stitching technique proposed by J.K. Ousterhout (1984) is extended for rectangular objects in interactive VLSI layout editors to L-shaped objects, thus providing added flexibility in the design of VLSI circuits. It is shown theoretically that the authors' method for handling L-shaped objects is more space-efficient than an alternative method based on a direct application of the original corner-stitching method.>

A csdawg for circular strings, which is obtained by making simple modifications to the compact symmetric directed acyclic word graph (csdawg) for linear strings, is proposed. This data structure does not contain extraneous vertices and, consequently, avoids the disadvantages of previous methods. Using this method, algorithms which make use of the csdawg for linear strings can then be extended to circular strings with trivial modifications. The extended algorithms continue to have the same time and space complexities. Moreover, the extensions take the form of postprocessing or preprocessing steps which are simple to add on to a system built for linear strings, particularly in an object-oriented language.>