Due to most of the existing graph repartitioning methods are known for poor efficiency in distributed environments. In this paper, we introduce a new graph repartitioning method with two phases in distributed environments. In the first phase, a local method is designed to identify all the potential candidate vertices that should be moved to the other partitions at once in each partition locally. In the second phase, a streaming graph processing model is adopted to reassign the candidate vertices to achieve lightweight graph repartitioning. During the reassignment of the vertex, we propose an objective function to balance both the load balance and the number of crossing edges among the distributed partitions. The experimental results with a large set of real word and synthetic graph datasets show that the communication cost can be reduced by nearly 1 to 2 orders of magnitude compared with the existing methods.

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

Many applications of wireless sensor networks (WSNs) require secure communication. The tree-based key management scheme, which is a symmetric key scheme, provides backward and forward secrecy. The sensor nodes in the communication group share a secret key for encrypting messages. When the sensor nodes are added to or evicted from the group, the group key has to be updated by sending rekeying messages. In this paper, we propose a method of key tree structure (KTS) generation by considering the addition and eviction ratio of sensor nodes to reduce the number of rekeying messages, which is influenced by the structure of the tree. For this, we define an extension of an existing tree structure such as a binary or ternary tree and generate KTS using an A* algorithm. To reduce the energy consumed by the message transmission, we also exploit genetic algorithm (GA) to build a secure communication group by considering the KTS. In the paper, we show the effectiveness of the proposed method compared with the existing structure via the simulation in terms of memory usage, the number of rekeying messages and energy consumption.

Segmenting indicated objects from natural color images remains a challenging problem for researches of image processing. In this paper, a novel level set approach is presented, to address this issue. In this segmentation algorithm, a contour that lies inside a particular region of the concerned object is first initialized by a user. The level set model is then applied, to extract the object of arbitrary shape and size containing this initial region. Constrained on the position of the initial contour, our proposed framework combines two particular energy terms, namely local and global energy, in its energy functional, to control movement of the contour toward object boundaries. These energy terms are mainly based on graph partitioning active contour models and Bhattacharyya flow, respectively. Its flow describes dissimilarities, measuring correlative relationships between the region of interest and surroundings. The experimental results obtained from our image collection show that the suggested method yields accurate and good performance, or better than a number of segmentation algorithms, when applied to various natural images.

There are a great amount of various resources described in many different ways for service oriented grid environment, while traditional grid resource discovery methods could not fit more complex future grid system. Therefore, this paper proposes a novel grid resource discovery method based on association rule hypergraph partitioning algorithm which analyzes user behavior in history transaction records to provide personality service for user. And this resource discovery method gives a new way to improve resource retrieval and management in grid research.

The graph partitioning problem is a famous combinatorial problem and has many applications including VLSI circuit design, task allocation in distributed computer systems and so on. In this paper, a novel neural network for the m-way graph partitioning problem is proposed where the maximum neuron model is used. The undirected graph with weighted nodes and weighted edges is partitioned into several subsets. The objective of partitioning is to minimize the sum of weights on cut edges with keeping the size of each subset balanced. The proposed algorithm was compared with the genetic algorithm. The experimental result shows that the proposed neural network is better or comparable with the other existing methods for solving the m-way graph partitioning problem in terms of the computation time and the solution quality.

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.