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 and its corresponding line graph.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3927507&req=5

f1-sensors-08-00635: A graph and its corresponding line graph.

Mentions: Let us assume that we have a graph of which all the nodes are numbered and all the edges are labeled distinctly. In this case its line graph is the graph obtained by replacing each edge with a corresponding single node and each node with some number of edges proportional to the degree of the respective node. An example graph G and its corresponding line graph L(G) are depicted in Figure 1.


Vertex Separators for Partitioning a Graph
A graph and its corresponding line graph.
© Copyright Policy
Related In: Results  -  Collection

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

f1-sensors-08-00635: A graph and its corresponding line graph.
Mentions: Let us assume that we have a graph of which all the nodes are numbered and all the edges are labeled distinctly. In this case its line graph is the graph obtained by replacing each edge with a corresponding single node and each node with some number of edges proportional to the degree of the respective node. An example graph G and its corresponding line graph L(G) are depicted in Figure 1.

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.