| 1. |
- Fjällström, Per-Olof
(författare)
-
Algorithms for Graph Partitioning: A Survey
- 1998
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The graph partitioning problem is as follows. Given a graph G = (N, E) (where N is a set of weighted nodes and E is a set of weighted edges) and a positive integer p , find p subsets N1 , N2 ,... Np of N such thatthe union set of Ni where i = 1...p equals N and Ni is disjoint from Nj for i =/ j , W(i)~W/p where i = 1, 2...p , where W(i) and W are the sums of the node weights in Ni and N , respectively,the cut size, i.e., the sum of the weights of edges crossing between subsets is minimized.This problem is of interest in areas such as VLSI placement and routing, and efficient parallel implementations of finte element methods. In this survey we summarize the state-of-the-art of sequential and parallel graph partitioning problems.
|
|
| 2. |
- Fjällström, Per-Olof, 1954-, et al.
(författare)
-
Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering
- 1998
-
Ingår i: International Journal of Computational Geometry & Applications. - : World Scientific Publishing Co. Pte. Ltd.. - 0218-1959. ; 8:1, s. 67-83
-
Tidskriftsartikel (refereegranskat)abstract
- Contact searching is an important and time-consuming part of computer simulation of certain deformation processes. Contact searching can be facilitated by orthogonal range searching. We have experimentally evaluated four methods for orthogonal range searching: the projection method, the cell method, the k-d tree method, and the range tree method. The results of our experiments indicate that two of these methods, the cell and k-d tree methods, have practical significance. The cell method is in most cases faster than the k-d tree method.
|
|
| 3. |
- Fjällström, Per-Olof
(författare)
-
Parallel Algorithms for Searching Monotone Matrices on Coarse Grained Multicomputers
- 1998
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present parallel algorithms for geometric problems on coarse grained multicomputers. More specifically, for a square mesh-connected p-processor computer, we show that:The implicit row maxima problem on a totally monotone n × n matrix can be solved in O((n/p) log p) time, if n > p2 .The all-farthest-neighbors problem for a convex n -gon can be solved in O(n/sqrt(p)) time, if n > p2/4 .The maximum-perimeter triangle inscribed in a convex n -gon can be found in O(n/sqrt(p)) time, if n > p2 .The solutions to the two latter problems are based on the reduction of these problems to searching problems in totally monotone matrices
|
|
