Accession Number : ADA132500

Title :   On Bisecting Random Graphs.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Bui,Thang Nguyen

PDF Url : ADA132500

Report Date : Feb 1983

Pagination or Media Count : 43

Abstract : A bisection of a graph with an even number of vertices is a partition of the vertex set into two disjoint sets of equal size. Given a bisection, the number of edges having one end in each of the two subsets of the bisection is called the size of the bisection. The bisection size of a graph is the minimum size of all possible bisections of the graph. Given a graph with an even number of vertices and a positive integer, the graph bisection problem is the problem of determining if the bisection size of the graph is less than the given number. The graph bisection problem is known to be NP-hard. In this thesis, we give probabilistic lower bounds and upper bounds for the bisection size of random graphs, graphs in which an edge appears between any two vertices with a certain fixed probability, say p, independent of all other edges. Upper bound and lower bound on the bisection size are given in the case p is a function of n. We also consider some heuristics for solving the graph bisection problem.

Descriptors :   *Graphs, *Probability, Computer graphics, Heuristic methods, Algorithms, Theses

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE