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 ：
It has been conjectured that for each positive integer k and each tree T with bipartite (Z1,Z2), every k-connected bipartite graph G with delta(G)>= k+max{|Z1|,|Z2|} admits a subgraph T 'congruent to T such that G-V(T ') is still k-connected. In this paper, we generalize the ear decompositions of 2-connected graphs into a (k,ak)-extensible system for a general k-connected graph. As a result, we confirm the conjecture for k <= 3 by proving a slightly stronger version of it.
Keyword ：
bipartite graphs bipartite graphs k-connected k-connected rooted forest rooted forest
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hong, Yanmei , Wu, Yihong , Liu, Qinghai . Redundant Trees in Bipartite Graphs [J]. | MATHEMATICS , 2025 , 13 (6) . |
| MLA | Hong, Yanmei et al. "Redundant Trees in Bipartite Graphs" . | MATHEMATICS 13 . 6 (2025) . |
| APA | Hong, Yanmei , Wu, Yihong , Liu, Qinghai . Redundant Trees in Bipartite Graphs . | MATHEMATICS , 2025 , 13 (6) . |
| 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 ：
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 ：
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 ：
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 ：
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 ：
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 ：
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 ：
Abstract ：
Motivated by recent progresses on study of factors and spectral extremal graph theory, in this paper, we focus on distance spectral extrema of k-factors in bipartite graphs for small k. First of all, we aim to investigate the existence of 1-factor in a bipartite graph with given minimum degree in terms of its distance spectral radius, which generalize and improve the previous result in [37]. Then we determine the extremal graph attaining the minimum distance spectral radius among all bipartite graphs with a unique perfect matching. Notice that a 2-factor consists of some vertex -disjoint cycles. As a beginning, we naturally consider some propositions of vertex-disjoint cycles and give a sufficient condition for the existence of two vertex-disjoint cycles in a bipartite graph with respect to the distance spectral radius. (c) 2022 Elsevier Inc. All rights reserved.
Keyword ：
1-factor 1-factor Distance spectral radius Distance spectral radius Vertex-disjoint cycles Vertex-disjoint cycles
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhang, Yuke , Lin, Huiqiu , Liu, Qinghai et al. Distance spectrum, 1-factor and vertex-disjoint cycles [J]. | LINEAR ALGEBRA AND ITS APPLICATIONS , 2022 , 654 : 10-27 . |
| MLA | Zhang, Yuke et al. "Distance spectrum, 1-factor and vertex-disjoint cycles" . | LINEAR ALGEBRA AND ITS APPLICATIONS 654 (2022) : 10-27 . |
| APA | Zhang, Yuke , Lin, Huiqiu , Liu, Qinghai , Zheng, Jinfeng . Distance spectrum, 1-factor and vertex-disjoint cycles . | LINEAR ALGEBRA AND ITS APPLICATIONS , 2022 , 654 , 10-27 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
