Name
Abstract | ||
|---|---|---|
When executing processes on parallel computer systems a major bottleneck is interprocessor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of (\V\/2k) Sigma(i=1)(k)lambda(i) for the k-section width of a graph is well known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define a global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/s00224-003-1083-9 | THEORY OF COMPUTING SYSTEMS |
Keywords | Field | DocType |
lower bound,parallel computer | Adjacency matrix,Discrete mathematics,Graph,Process graph,Combinatorics,Line graph,Upper and lower bounds,Level structure,Pathwidth,Mathematics,Eigenvalues and eigenvectors | Journal |
Volume | Issue | ISSN |
36.0 | 5 | 1432-4350 |
Citations | PageRank | References |
1 | 0.40 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Elsässer | 1 | 70 | 6.04 |
| Thomas Lücking | 2 | 353 | 28.79 |
| Burkhard Monien | 3 | 2199 | 279.35 |