Limits...
Vertex Separators for Partitioning a Graph

View Article: PubMed Central - PubMed

ABSTRACT

Finite Element Method (FEM) is a well known technique extensively studied for spatial and temporal modeling of environmental processes, weather prediction computations, and intelligent signal processing for wireless sensors. The need for huge computational power arising in such applications to simulate physical phenomenon correctly mandates the use of massively parallel computers to distribute the workload evenly. In this study, a novel heuristic algorithm called Line Graph Bisection which partitions a graph via vertex separators so as to balance the workload amongst the processors and to minimize the communication overhead is proposed. The proposed algorithm is proved to be computationally feasible and makes cost-effective parallel implementations possible to speed up the solution process.

No MeSH data available.


A graph for comparing KLB and LGB.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3927507&req=5

f17-sensors-08-00635: A graph for comparing KLB and LGB.

Mentions: In Figure 17, an example graph with 40 nodes and 96 edges is depicted. KLB when presented with that input finds the minimum cut of size 8 which happens to be the optimal solution in that case as shown in dotted red line in Figure 17. This may be used to obtain the vertex separator including nodes 33, 34, 35, 36, 37, 38, 39, and 40. LGB, on the other hand, when supplied with this specific example graph finds a vertex separator with nodes 17, 18, 19, and 20 of size 4 which is half the size of that found by KLB. In order for KLB to obtain that solution, it would have to overlook the optimal and be content with a sub optimal solution of size 12. There exists a proliferation of such cases that clearly justifies the need for LGB.


Vertex Separators for Partitioning a Graph
A graph for comparing KLB and LGB.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3927507&req=5

f17-sensors-08-00635: A graph for comparing KLB and LGB.
Mentions: In Figure 17, an example graph with 40 nodes and 96 edges is depicted. KLB when presented with that input finds the minimum cut of size 8 which happens to be the optimal solution in that case as shown in dotted red line in Figure 17. This may be used to obtain the vertex separator including nodes 33, 34, 35, 36, 37, 38, 39, and 40. LGB, on the other hand, when supplied with this specific example graph finds a vertex separator with nodes 17, 18, 19, and 20 of size 4 which is half the size of that found by KLB. In order for KLB to obtain that solution, it would have to overlook the optimal and be content with a sub optimal solution of size 12. There exists a proliferation of such cases that clearly justifies the need for LGB.

View Article: PubMed Central - PubMed

ABSTRACT

Finite Element Method (FEM) is a well known technique extensively studied for spatial and temporal modeling of environmental processes, weather prediction computations, and intelligent signal processing for wireless sensors. The need for huge computational power arising in such applications to simulate physical phenomenon correctly mandates the use of massively parallel computers to distribute the workload evenly. In this study, a novel heuristic algorithm called Line Graph Bisection which partitions a graph via vertex separators so as to balance the workload amongst the processors and to minimize the communication overhead is proposed. The proposed algorithm is proved to be computationally feasible and makes cost-effective parallel implementations possible to speed up the solution process.

No MeSH data available.