Graph designs for all graphs with six vertices and eight edges are discussed. The existence of these graph designs are completely solved except in two possible cases of order 32.
The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of ...The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of mechanisms based on graph theory and polynomial operation.The graph framework of the synthesis approach is built firstly,and it involves:(1)the kinematic function units extracted from mechanisms;(2)the kinematic link graph that transforms the synthesis problem from mechanical domain into graph domain;(3)two graph representations,i.e.,walk representation and path representation,of design candidates;(4)a weighted matrix theorem that transforms the synthesis process into polynomial operation.Then,the formulas and algorithm to the polynomial operation are presented.Based on them,the computational flowchart to the synthesis approach is summarized.A design example is used to validate and illustrate the synthesis approach in detail.The proposed synthesis approach is not only supportive to enumerate the design candidates to the conceptual design of a mechanical system exhaustively and automatically,but also helpful to make that enumeration process computable.展开更多
The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism a...The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decomposed into sub-graphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. Key words design pattern mining - attributed relational graph - subgraph isomorphism CLC number TP 311.5 Foundation item: Supported by the National Natural Science Foundation of China (60273075) and the Science Foundation of Naval University of Engineering (HGDJJ03019)Biography: LI Qing-hua (1940-), male, Professor, research direction: parallel computing.展开更多
Multi-component mooring systems become widely used in deep water position-keeping of drilling and production platforms. However, versatile materials make it difficult to design appropriate mooring lines made of severa...Multi-component mooring systems become widely used in deep water position-keeping of drilling and production platforms. However, versatile materials make it difficult to design appropriate mooring lines made of several segments. Based on catenary equations of a multi-component mooring line at a specific water depth, this paper establishes a minimum model for designing this kind of lines. The model is solved by Genetic Algorithm and Multi-Objective Planning respectively. The model is verified by its application to a practical mooring design assignment—a quasi-static analysis for a large semi-submersible. The optimal result is finally obtained with the aid of design graphs.展开更多
The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</su...The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</sub>-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star<sub>123</sub>, P<sub>7</sub>-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.展开更多
<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is...<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on d vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> , we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.展开更多
The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) t...The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.展开更多
We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minim...We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.展开更多
基金Supported by the Natural Science Foundation of China （No.10371031） and Natural Science Foundation of Hebei （No.103146）.
文摘Graph designs for all graphs with six vertices and eight edges are discussed. The existence of these graph designs are completely solved except in two possible cases of order 32.
基金Supported by State Key Program of National Natural Science Foundation of China(Grant No.51535009)111 Project of China(Grant No.B13044).
文摘The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of mechanisms based on graph theory and polynomial operation.The graph framework of the synthesis approach is built firstly,and it involves:(1)the kinematic function units extracted from mechanisms;(2)the kinematic link graph that transforms the synthesis problem from mechanical domain into graph domain;(3)two graph representations,i.e.,walk representation and path representation,of design candidates;(4)a weighted matrix theorem that transforms the synthesis process into polynomial operation.Then,the formulas and algorithm to the polynomial operation are presented.Based on them,the computational flowchart to the synthesis approach is summarized.A design example is used to validate and illustrate the synthesis approach in detail.The proposed synthesis approach is not only supportive to enumerate the design candidates to the conceptual design of a mechanical system exhaustively and automatically,but also helpful to make that enumeration process computable.
文摘The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decomposed into sub-graphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. Key words design pattern mining - attributed relational graph - subgraph isomorphism CLC number TP 311.5 Foundation item: Supported by the National Natural Science Foundation of China (60273075) and the Science Foundation of Naval University of Engineering (HGDJJ03019)Biography: LI Qing-hua (1940-), male, Professor, research direction: parallel computing.
文摘Multi-component mooring systems become widely used in deep water position-keeping of drilling and production platforms. However, versatile materials make it difficult to design appropriate mooring lines made of several segments. Based on catenary equations of a multi-component mooring line at a specific water depth, this paper establishes a minimum model for designing this kind of lines. The model is solved by Genetic Algorithm and Multi-Objective Planning respectively. The model is verified by its application to a practical mooring design assignment—a quasi-static analysis for a large semi-submersible. The optimal result is finally obtained with the aid of design graphs.
文摘The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</sub>-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star<sub>123</sub>, P<sub>7</sub>-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.
文摘<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on d vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> , we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.
文摘The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.
文摘We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.
