Computational & Technology Resources
an online resource for computational,
engineering & technology publications |
|
Civil-Comp Proceedings
ISSN 1759-3433 CCP: 93
PROCEEDINGS OF THE TENTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL STRUCTURES TECHNOLOGY Edited by:
Paper 260
Regular Graphs Factorization for Partitioning M. Mahdavinia and Y. Navabzadeh Esmaeely
Department of Civil Engineering, Iran University of Science and Technology, Narmak, Tehran, Iran M. Mahdavinia, Y. Navabzadeh Esmaeely, "Regular Graphs Factorization for Partitioning", in , (Editors), "Proceedings of the Tenth International Conference on Computational Structures Technology", Civil-Comp Press, Stirlingshire, UK, Paper 260, 2010. doi:10.4203/ccp.93.260
Keywords: factorization, regular graphs, generators, graph product, graph partitioning, MRSRT.
Summary
Many structures have regular patterns and can be viewed as a graph model. One can work on the graphical model of a structure instead of the main structure resulting in simplification in various problems in combinatorial optimization such as ordering, graph partitioning and domain decomposition for finite element models.
Graph partitioning is problem with numerous applications. It appears in various forms of parallel computing, sparse matrix reordering, circuit placement and other important disciplines. The problem consists of dividing a graph in a certain number of non-overlapping partitions minimizing the number of cuts after the division and balancing the load associated to each one of them. Different algorithms for the resolution of this problem have been proposed but in all of them it is difficult to know the quality of the solution found, since this is a NP-complete problem [1,2]. In this paper efficient algorithms are presented for identifying the generators of regular graph models G formed by Cartesian or strong Cartesian graph products. These algorithms are based on using definitions of graph theory and algebraic graph theory such as MRSRT and Fiedler vector. This process of identification is called the factorization of G and the generators are known as the factors of G. Most of structural models are regular and can be considered as the product of some simple graphs such as paths and/or cycles. By finding the factors of given graph G, certain problems in structural mechanics can be solved more efficiently [3]. Once such a factorization is performed, a new approach is employed for partitioning graph G. The efficiently of the method presented is illustrated through eight examples of different configurations. References
purchase the full-text of this paper (price £20)
go to the previous paper |
|