Oregon State University

Calendar

Calendars

Event Details

PhD Oral Preliminary Examination – Theresa Migler VanDollen


Monday, November 12, 2012 11:00 AM - 1:00 PM

Density and Dense Subgraphs
In the proposed research we will discuss the density of graphs. The density of a graph is the ratio of edges to vertices in the graph. We begin by observing density characteristics of real graphs. We use our observations to create random graph models that more accurately simulate various attributes of real-world graphs. Then we discuss the well-studied densest subgraph problems. It is of great interest to find the densest subgraph of a given graph. For example, in a network that models academic collaboration, authors within the densest component of the graph tend to be the most prolific. Finding the densest subgraph of a given graph is easy, it can be done in polynomial time. However, when the number of vertices in the densest subgraph is restricted, say we wish to find the densest subgraph on k vertices, the problem becomes much more difficult. This problem is so difficult that in order to make progress toward a PTAS, we must restrict the domain. We consider the restricted size densest subgraph problems on planar graphs. Finally, we see that this restriction is still difficult, so we consider other "select k'' types of problems, the most promising of which is the k-MST problem.

Major Advisor: Glencora Borradaile
Committee: Prasad Tadepalli
Committee: Alan Fern
Committee: Holly Swisher
GCR: Harry Yeh 


Kelley Engineering Center (campus map)
4107
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: