Degree Type

Thesis

Date of Award

2012

Degree Name

Master of Science

Department

Computer Science

First Advisor

Oliver Eulenstein

Abstract

One important computational problem is that of mining quasi bicliques from bipartite graphs. It is important because it has an almost endless number of applications and, in most real world problems, is more appropriate than the mining of bicliques. In my thesis I examine the following: the motivation for quasi bicliques, the existing literature for quasi bicliques, my implementation of a web application that allows the user to compute exact quasi biclique solutions using the biclique formulation and the exact solution algorithm provided by Chang et al.[1], and finally a polynomial heuristic algorithm for finding large quasi bicliques in the special case where we have all the biclique subgraphs of a bipartite graph available.

Copyright Owner

Nick Pappas

Language

en

File Format

application/pdf

File Size

50 pages

Share

COinS