Edit distance and its computation

József Balogh, Ryan Martin

Research output: Contribution to journalArticlepeer-review


In this paper, we provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without using Szemerédi's Regularity Lemma directly. Using this new method, we are able to compute the edit distance from hereditary properties for which it was previously unknown. For some graphs H, the edit distance from Forb(H) is computed, where Forb(H) is the class of graphs which contain no induced copy of graph H. Those graphs for which we determine the edit distance asymptotically are H = Ka + E b, an a-clique with b isolated vertices, and H = K3,3, a complete bipartite graph. We also provide a graph, the first such construction, for which the edit distance cannot be determined just by considering partitions of the vertex set into cliques and cocliques. In the process, we develop weighted generalizations of Turán's theorem, which may be of independent interest.

Original languageEnglish (US)
Article numberR20
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - Jan 28 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Edit distance and its computation'. Together they form a unique fingerprint.

Cite this