Can’t find an event? We’re busy migrating to a new event calendar. Try looking at the new calendar
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 realworld graphs. Then we discuss the wellstudied 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
kMST 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 