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 configuration where bipartite graph matching gets stuck at a local minimum.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3927507&req=5

f18-sensors-08-00635: A configuration where bipartite graph matching gets stuck at a local minimum.

Mentions: Other cases, however, may be plotted where bipartite graph matching cannot escape from local minima as depicted in Figure 18. An optimal solution for the graph presented in Figure 18 would have a single node, namely, 9 in the vertex separator. Bipartite graph matching, when applied from the initial configuration depicted in Figure 18, nevertheless, cannot find a set of nodes in either partition whose size is smaller than the set of adjacent nodes in the separator.


Vertex Separators for Partitioning a Graph
A configuration where bipartite graph matching gets stuck at a local minimum.
© Copyright Policy
Related In: Results  -  Collection

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

f18-sensors-08-00635: A configuration where bipartite graph matching gets stuck at a local minimum.
Mentions: Other cases, however, may be plotted where bipartite graph matching cannot escape from local minima as depicted in Figure 18. An optimal solution for the graph presented in Figure 18 would have a single node, namely, 9 in the vertex separator. Bipartite graph matching, when applied from the initial configuration depicted in Figure 18, nevertheless, cannot find a set of nodes in either partition whose size is smaller than the set of adjacent nodes in the separator.

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.