University of Cambridge > Talks.cam > Combinatorics Seminar > Recent results on the edit distance of graphs

Recent results on the edit distance of graphs

Add to your list(s) Download to your calendar using vCal

  • UserRyan Martin (Iowa State University)
  • ClockThursday 14 October 2010, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

In this talk, we will discuss the edit distance function, a function of a hereditary property $\mathcal{H}$ and of $p$, which measures the maximum proportion of edges in a density-$p$ graph that need to be inserted/deleted in order to transform it into a member of $\mathcal{H}$. We will describe a method of computing this function and give some results that have been attained using this method. The edit distance problem has applications in property testing and evolutionary biology and is closely related to well-studied Tur\’an-type problems. This is joint work with Tracy McKay, Iowa State University.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity