Query：
学者姓名：刘清海
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
Abstract ：
The Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical to PCB design. Primary methods based on integer linear programming (ILP) work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, traditional ILP strategies frequently cause time violations as the number of variables increases due to time-consuming preprocessing. In addition, heuristic algorithms have a time advantage when dealing with specific problems. In this paper, We propose an efficient two-stage escape routing method that employs LP for global routing and uses a heuristic algorithm to deal with the path intersection problem to minimize wiring length and runtime for large-scale PCBs. We first model the OER problem as a min-cost multi-commodity flow problem and use ILP to solve it. Then, we relax the non-crossing constraints and transform the ILP model into an LP model to reduce the runtime. we also construct a crossing graph according to the intersection of routing paths and propose a heuristic algorithm to locate congestion quickly. Finally, we reduce the local area capacity and allow global automatic congestion optimization. Compared with the state-of-the-art work, experimental results show that our method can reduce the routing time by 60% and handle larger-scale PCB escape routing problems.
Keyword ：
Heuristic algorithm Heuristic algorithm Linear programming Linear programming Min-cost multi-commodity flow Min-cost multi-commodity flow Ordered escape routing Ordered escape routing
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lin, Disi , Chen, Chuandong , Wei, Rongshan et al. Two stage Ordered Escape Routing combined with LP and heuristic algorithm for large scaled PCB [J]. | INTEGRATION-THE VLSI JOURNAL , 2025 , 100 . |
| MLA | Lin, Disi et al. "Two stage Ordered Escape Routing combined with LP and heuristic algorithm for large scaled PCB" . | INTEGRATION-THE VLSI JOURNAL 100 (2025) . |
| APA | Lin, Disi , Chen, Chuandong , Wei, Rongshan , Liu, Qinghai , He, Huan , Zhu, Ziran et al. Two stage Ordered Escape Routing combined with LP and heuristic algorithm for large scaled PCB . | INTEGRATION-THE VLSI JOURNAL , 2025 , 100 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
As a variant of the Ulam-Kelly's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetkovie and Schwenk posed independently the following problem: can the characteristic polynomial of a simple graph G with vertex set V be reconstructed from the characteristic polynomials of all subgraphs in {G - v | v is an element of V} for |V| >= 3? This problem is still open. A natural problem is: can the characteristic polynomial of a simple graph G with edge set E be reconstructed from the characteristic polynomials of all subgraphs in {G - e|e is an element of E}? In this paper, we prove that if |V| not equal |E|, then the characteristic polynomial of G can be reconstructed from the characteristic polynomials of all subgraphs in {G - uv, G - u - v|uv is an element of E}, and the similar result holds for the permanental polynomial of G. We also prove that the Laplacian (resp. signless Laplacian) characteristic polynomial of G can be reconstructed from the Laplacian (resp. signless Laplacian) characteristic polynomials of all subgraphs in {G - e|e is an element of E} (resp. if |V| not equal |E|). (c) 2024 Elsevier B.V. All rights reserved.
Keyword ：
Characteristic polynomial Characteristic polynomial Edge reconstruction conjecture Edge reconstruction conjecture Laplacian characteristic polynomial Laplacian characteristic polynomial Vertex reconstruction conjecture Vertex reconstruction conjecture
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhang, Jingyuan , Jin, Xian'an , Yan, Weigen et al. On the edge reconstruction of the characteristic and permanental polynomials of a simple graph [J]. | DISCRETE MATHEMATICS , 2024 , 347 (9) . |
| MLA | Zhang, Jingyuan et al. "On the edge reconstruction of the characteristic and permanental polynomials of a simple graph" . | DISCRETE MATHEMATICS 347 . 9 (2024) . |
| APA | Zhang, Jingyuan , Jin, Xian'an , Yan, Weigen , Liu, Qinghai . On the edge reconstruction of the characteristic and permanental polynomials of a simple graph . | DISCRETE MATHEMATICS , 2024 , 347 (9) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Gallai's conjecture asserts that every connected graph of order n can be decomposed into inverted right perpendicularn/2inverted left perpendicular paths. A graph G is k -degenerated if each subgraph admits a vertex with degree no more than k . In this paper, we characterize the graphs that contain a path through specified edges. As a result, we prove that a connected 3-degenerated graph of order n that is not isomorphic to K-3 or K-5(-) can be decomposed into left perpendicularn/2right perpendicular paths, which extends three theorems of [2,3,12]. (c) 2024 Elsevier B.V. All rights reserved.
Keyword ：
3-degenerated 3-degenerated Gallai's conjecture Gallai's conjecture Path-decomposition Path-decomposition
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhang, Junhao , Liu, Qinghai , Hong, Yanmei . Gallai's conjecture for 3-degenerated graphs [J]. | DISCRETE MATHEMATICS , 2024 , 347 (7) . |
| MLA | Zhang, Junhao et al. "Gallai's conjecture for 3-degenerated graphs" . | DISCRETE MATHEMATICS 347 . 7 (2024) . |
| APA | Zhang, Junhao , Liu, Qinghai , Hong, Yanmei . Gallai's conjecture for 3-degenerated graphs . | DISCRETE MATHEMATICS , 2024 , 347 (7) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Mader proved that, for any tree T of order m $m$, every k -connected graph G with delta( G ) >= 2 (k + m - 1 )( 2) + m - 1 contains a subtree T ' congruent to T such that G - V( T ' ) is k-connected. We proved that any graph G with minimum degree delta( G ) >= 2 k contains k-connected triples. As a corollary, we prove that, for any tree T of order m , every k -connected graph G with delta( G ) >= 3 k + 4 m - 6 contains a subtree T ' congruent to T such that G - V( T ' )-is still k -connected, improving Mader's condition to a linear bound.
Keyword ：
connectivity-keeping trees connectivity-keeping trees k-connected k-connected k-connected triples k-connected triples
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Liu, Qinghai , Ying, Kai , Hong, Yanmei . Highly connected triples and Mader's conjecture [J]. | JOURNAL OF GRAPH THEORY , 2024 , 107 (3) : 478-484 . |
| MLA | Liu, Qinghai et al. "Highly connected triples and Mader's conjecture" . | JOURNAL OF GRAPH THEORY 107 . 3 (2024) : 478-484 . |
| APA | Liu, Qinghai , Ying, Kai , Hong, Yanmei . Highly connected triples and Mader's conjecture . | JOURNAL OF GRAPH THEORY , 2024 , 107 (3) , 478-484 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Escape routing is a crucial step in printed circuit board (PCB) design. In response to the issues of low wiring efficiency in large-scale pin array circuit board routing where multiple devices synchronization is not considered in the current escape algorithm, this paper proposes a simultaneous escape routing algorithm based on weighted maximum independent set. Firstly, a path conflict graph is constructed by projecting paths correlated to pin pairs, followed by obtaining layered ordering results using the weighted maximum independent set model. Subsequently, channel estimation and channel optimization are performed using depth-first search in different directions. Finally, an escape routing is conducted using a detailed grid-based wiring method. Experimental results demonstrate that the proposed algorithm achieves a near 100% successful routing rate for large-scale pin array PCB cases. It outperforms the minimum cost multi-commodity flow (MMCF) algorithm and the sequential escape algorithm with estimated functions by an average improvement of 10% in wire length.
Keyword ：
Channel planning Channel planning Layered ordering Layered ordering Maximum independent set Maximum independent set Simultaneous escape routing Simultaneous escape routing
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Yang, Ze , Hu, Kunwei , Liu, Qinghai et al. Simultaneous Escape Routing Algorithm for Large-scale Pin Arrays [J]. | 2024 INTERNATIONAL SYMPOSIUM OF ELECTRONICS DESIGN AUTOMATION, ISEDA 2024 , 2024 : 386-391 . |
| MLA | Yang, Ze et al. "Simultaneous Escape Routing Algorithm for Large-scale Pin Arrays" . | 2024 INTERNATIONAL SYMPOSIUM OF ELECTRONICS DESIGN AUTOMATION, ISEDA 2024 (2024) : 386-391 . |
| APA | Yang, Ze , Hu, Kunwei , Liu, Qinghai , Chen, Jiarui . Simultaneous Escape Routing Algorithm for Large-scale Pin Arrays . | 2024 INTERNATIONAL SYMPOSIUM OF ELECTRONICS DESIGN AUTOMATION, ISEDA 2024 , 2024 , 386-391 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Hasunuma conjectured that for any tree of order m and for any k-connected (resp. k-edge-connected) graph G, if delta(G)>= k+m-1 then G contains a subgraph H congruent to T such that G-E(H) is k-connected (resp. k-edge-connected). Hasunuma verified the conjecture for k=1,2. In this paper, we confirm the conjecture when k=3.
Keyword ：
Connectivity Connectivity Subdivision Subdivision Trees Trees
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Liu, Haiyang , Liu, Qinghai , Hong, Yanmei . Connectivity keeping trees in 3-connected or 3-edge-connected graphs [J]. | DISCRETE MATHEMATICS , 2023 , 346 (12) . |
| MLA | Liu, Haiyang et al. "Connectivity keeping trees in 3-connected or 3-edge-connected graphs" . | DISCRETE MATHEMATICS 346 . 12 (2023) . |
| APA | Liu, Haiyang , Liu, Qinghai , Hong, Yanmei . Connectivity keeping trees in 3-connected or 3-edge-connected graphs . | DISCRETE MATHEMATICS , 2023 , 346 (12) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Escape routing is a critical problem in PCB routing, and its quality greatly affects the PCB design cost. Unlike the traditional escape routing that works mainly for the BGA package with unique line width and space, this paper presents a high-performance escape routing algorithm to handle problems with variable design rules and manual constraints, including variable line widths/spaces, the neck mode of wires, and the pad entry for differential pairs. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph. We then construct a bi-projection graph and propose a matching-based hierarchical sequencing algorithm to consider manual constraints. We perform global routing for each pin/differential pair by congestion-avoiding path initialization and rip-up and reroute path optimization. Finally, we complete detailed routing in every face, ensuring the wire angle and pad entry constraints. Experimental results show that our algorithm can achieve 100% routability without any design rule violation for all given industrial PCB instances, while two state-of-the-art routers cannot complete routing.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Liu, Qinghai , Lin, Disi , Chen, Chuandong et al. A Matching Based Escape Routing Algorithm with Variable Design Rules and Constraints [J]. | IEEE DESIGN AUTOMATION CONFERENCE, DAC , 2023 . |
| MLA | Liu, Qinghai et al. "A Matching Based Escape Routing Algorithm with Variable Design Rules and Constraints" . | IEEE DESIGN AUTOMATION CONFERENCE, DAC (2023) . |
| APA | Liu, Qinghai , Lin, Disi , Chen, Chuandong , He, Huan , Chen, Jianli , Chang, Yao-Wen . A Matching Based Escape Routing Algorithm with Variable Design Rules and Constraints . | IEEE DESIGN AUTOMATION CONFERENCE, DAC , 2023 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
G is a split graph if V (G) can be partitioned into a clique D and an independent set I. Let r(G) denote the toughness of a graph G. If a graph G contains two spanning trees T1, T2 such that for each two distinct vertices x, y of G, the (x, y)-path in each Ti has no common edge and no common vertex except for the two ends, then T1, T2 are called two completely independent spanning trees (CISTs) of G, i E {1, 2}. Several results have shown that some sufficient conditions for Hamiltonian graphs also guarantee the existence of two CISTs, which implies the Hamiltonicity and the existence of two CISTs of a graph have close connection. In this paper, we prove that if G is a Hamiltonian split graph with |D| > max{3, |I|}, then G contains two CISTs. Moreover, we show that if G is a Hamiltonian split graph with r(G) > 1, then G contains two CISTs. As a corollary, we obtain that every 32-tough split graph contains two CISTs.& COPY; 2023 Elsevier B.V. All rights reserved.
Keyword ：
Split graph Split graph Toughness Toughness Two CISTs Two CISTs
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Chen, Xiaodong , Liu, Qinghai , Yang, Xiwu . Two completely independent spanning trees of split graphs* [J]. | DISCRETE APPLIED MATHEMATICS , 2023 , 340 : 76-78 . |
| MLA | Chen, Xiaodong et al. "Two completely independent spanning trees of split graphs*" . | DISCRETE APPLIED MATHEMATICS 340 (2023) : 76-78 . |
| APA | Chen, Xiaodong , Liu, Qinghai , Yang, Xiwu . Two completely independent spanning trees of split graphs* . | DISCRETE APPLIED MATHEMATICS , 2023 , 340 , 76-78 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
PCB routing becomes time-consuming as the complexity of PCB design increases. Unlike traditional schemes that treat the two essential PCB routing processes separately, namely, escape and bus routing, we consider the continuity between them and present a golden-pin-based routing scheme to find the desired solution with angle and topology constraints. Further, conventional rip-up and reroute methods are often ineffective and inefficient for congestion alleviation and routability optimization. We construct a component graph by modeling components as vertices and applying the minimum weight vertex covering method to improve the routability. A self-adaptable ordering method is presented for escape routing to arrange the pin order on the component boundary, guaranteeing successful bus routing. In addition, escape routing is performed based on a disjoint path method. We construct a dynamic Hanan grid in bus routing and utilize a novel congestion adjustment technique to improve solution quality. Compared with FreeRouting and Allegro, the experiment results show that our algorithm achieves high routability and a significant 90% runtime reduction.
Keyword ：
bus routing bus routing disjoint path disjoint path escape routing escape routing
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Liu, Qinghai , Tang, Qinfei , Chen, Jiarui et al. Disjoint-Path and Golden-Pin Based Irregular PCB Routing with Complex Constraints [J]. | IEEE DESIGN AUTOMATION CONFERENCE, DAC , 2023 . |
| MLA | Liu, Qinghai et al. "Disjoint-Path and Golden-Pin Based Irregular PCB Routing with Complex Constraints" . | IEEE DESIGN AUTOMATION CONFERENCE, DAC (2023) . |
| APA | Liu, Qinghai , Tang, Qinfei , Chen, Jiarui , Chen, Chuandong , Zhu, Ziran , He, Huan et al. Disjoint-Path and Golden-Pin Based Irregular PCB Routing with Complex Constraints . | IEEE DESIGN AUTOMATION CONFERENCE, DAC , 2023 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Global routing is a critical problem in PCB routing, and its quality greatly affect the PCB design cost. Unlike existing methods based on traditional rectangular grid, this paper present a novel algorithm based on triangular grid model to handle the problem. We first propose a method to sort all the unconnected two-pin nets, then construct a triangular grid graph to represent the routing resources on the printed circuited board. Finally we use the idea of maximum flow to find the paths to complete global routing and use the detailed routing to get the result of completed wires. Experimental results show that our algorithm can spend less time than the two state-of-the-art routers without any design rule violations for all given industrial PCB instances. © 2023 IEEE.
Keyword ：
Printed circuit boards Printed circuit boards Printed circuit design Printed circuit design Routing algorithms Routing algorithms
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhou, Yujing , Liu, Qinghai , Zhang, Xinhong et al. A Global Routing Algorithm for PCB Based on Triangular Grid [C] . 2023 : 64-69 . |
| MLA | Zhou, Yujing et al. "A Global Routing Algorithm for PCB Based on Triangular Grid" . (2023) : 64-69 . |
| APA | Zhou, Yujing , Liu, Qinghai , Zhang, Xinhong , Chen, Jiarui . A Global Routing Algorithm for PCB Based on Triangular Grid . (2023) : 64-69 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
