Computer Engineering / Bilgisayar Mühendisliği

Permanent URI for this collectionhttps://hdl.handle.net/11147/10

Browse

Filters

20052

Settings

Author: search.filters.author.Marshall, GeoffreyDepartment: search.filters.department.İzmir Institute of Technology. Computer Engineering

Search Results

Now showing 1 - 2 of 2
  • Conference Object
    Citation - WoS: 3
    Citation - Scopus: 5
    Serial and Parallel Multilevel Graph Partitioning Using Fixed Centers
    (Springer Verlag, 2005) Erciyeş, Kayhan; Alp, Ali; Marshall, Geoffrey
    We present new serial and parallel algorithms for multilevel graph partitioning. Our algorithm has coarsening, partitioning and uncoarsening phases like other multilevel partitioning methods. However, we choose fixed nodes which are at least a specified distance away from each other and coarsen them with their neighbor nodes in the coarsening phase using various heuristics. Using this algorithm, it is possible to obtain theoretically and experimentally much more balanced partitions with substantially decreased total edge costs between the partitions than other algorithms. We also developed a parallel method for the fixed centered partitioning algorithm. It is shown that parallel fixed centered partitioning obtains significant speedups compared to the serial case.
  • Conference Object
    Implementation of a Cluster Based Routing Protocol for Mobile Networks
    (Springer Verlag, 2005) Marshall, Geoffrey; Erciyeş, Kayhan
    We show the implementation and the simulation results of a hierarchical, cluster based routing protocol for mobile ad hoc networks using Parallel Virtual Machine (PVM). The network represented by a graph is partitioned into clusters by a graph partitioning algorithm and the shortest routes are first calculated locally in each cluster in the first srep. The simplified network which consists only of the nodes that have connections to other clusters called the neighbor nodes is then formed and the shortest routes are calculated for this simple network as the second step. A complete route between the two nodes of different clusters is formed by the union of intra-cluster and inter-cluster routes. We show the implementation results using PVM where a workstation represents a cluster and each node is a PVM process. The results obtained support the theoretical considerations where the efficiency increases by the number of clusters in use.