# PCB Network Analysis for Circuit Partitioning
## 2 Related Work  
As mentioned above, the netlist is usually represented as a graph--a point set \(\mathbf{S}\) and an edge set \(\mathbf{E}\) between points and points, and the edge set \(\mathbf{E}\) can be attached with weights to become a weighted graph [6]. The existing netlist partitioning algorithms mainly consider two types of problems:  
1. How to divide, that is, the partition strategy;
2. How to reduce the time complexity of partition, that is, the partition efficiency [7]. Partition strategies can be roughly classified into four categories: methods based on graph cut by flow [8, 9, 10, 11], heuristic methods [1, 12], eigenvector method [13], and combinations of these methods [11, 14, 15, 16]. Generally, the methods based on graph cut have high time complexity, and the heuristic algorithms are relatively fast. All these types of algorithms can be combined into a multilevel framework [3, 11, 17, 18], which mainly divides the partition problem into multiple levels to reduce the scale of the problem, and leads to reduce the time complexity of partition. **Heuristic methods:** [PERSON] and [PERSON] proposed a netlist partition algorithm, called KL algorithm, which is the most classic of the heuristic methods [1]. The KL algorithm partitions components by evaluating a heuristic value \(D\), which is computed from the cost matrix, and it is a two-way partition approach applied to component partition on circuit boards. The KL algorithm was extended to different variations. [PERSON] et al. [19] used the KL algorithm to partition on mesh-based network-on-chip. [PERSON] and [PERSON] [20] considered a parallel KL algorithm to partition the component on very-large-scale integrated circuit (VLSI) for fast solution. [PERSON] and [PERSON] [21] extended the KL algorithm to 3D network-on-chip, while [PERSON] et al. extended the KL algorithm by using the balanced bi-partition theory of graphs, and improved it by giving a reasonable initial partition in the multilevel framework [22]. [PERSON] and [PERSON] in [12] proposed a cluster-based heuristic method. They extracted component attributes from netlist, including component terminal count, common net count, the number of nets localized, common net fanout, and so on, to identify strongly connected components to reduce the netlist complexity. **Graph cut methods:** Netlists are natural graphs with nodes and connection, so the traditional graph cut algorithms were easily taken to the netlist partition. [PERSON] and [PERSON] presented a partition method called ratio cut, and solved the ratio cut by linear programming techniques via the MaxFlow [23], while [PERSON] et al. ultilized the ratio cut in the hierarchical way in [11]. [PERSON] and [PERSON] [14] combined the min-cut and KL algorithm, and proposed an iterative min-cut heuristic method with a linear time, called FM algorithm. [PERSON] et al. [9] proposed a two-way partition strategy by solving a replication graph cut problem. [PERSON] et al. [3] presented a multilevel paradigm of coarse-to-coarser to partition hypergraph in VLSI with over 100k vertices. [PERSON] et al. [4] provided an implementation of hypergraph partition in VLSI. However, these methods only treated the netlist as a pure graph, so only the geometric connection of the netlist was considered in the partition process. **Eigenvector methods:** [PERSON] et al. approximated the netlist as a weighted graph, and initially partitioned the weighted graph into k blocks of fixed module size by the eigenvector technique of [PERSON] [6]; they also gave the lower bounds on the number of cut nets using the tightly underestimated graph approximation and the simple eigenanalysis results [13]. **Other methods:** Monolithic 3D (M3D) integrated circuits are a promising technology that improves integration density greatly, which is orders of magnitude higher than that offered by through-silicon-vias, so the partition of M3D netlists has attracted a number of researchers [19; 24; 25; 26]. [PERSON] et al.