Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 93
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

Full Bibliographic Reference for this paper
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.

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.

A. Kaveh, "Structural mechanics: Graph and Matrix Methods",2nd edition, Research Studies Press, UK, 1995.
A. Kaveh, "Optimal Structural Analysis", 2nd edition, Research Studies Press, UK, 2005.
A. Kaveh, H. Rahami, "An efficient method for decomposition of regular structures using graph products", Int. J. Numer. Methods Eng., 61, 1797-1808, 2004. doi:10.1002/nme.1126

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £145 +P&P)