On Bisecting Random Graphs.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1983
- Accession Number
- ADA132500
Entities
People
- Thang Nguyen Bui
Organizations
- Massachusetts Institute of Technology