{
  "id": "1012.3716",
  "version": "v3",
  "published": "2010-12-16T18:48:22.000Z",
  "updated": "2014-09-27T20:18:17.000Z",
  "title": "On the computation of edit distance functions",
  "authors": [
    "Ryan Martin"
  ],
  "comment": "25 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The edit distance function of hereditary property, $\\mathcal{H}$, is a function of $p\\in[0,1]$ and is the limit of the maximum normalized distance between a graph of density $p$ and $\\mathcal{H}$. This paper uses localization, for computing the edit distance function of various hereditary properties. For any graph $H$, ${\\rm Forb}(H)$ denotes the property of not having an induced copy of $H$. We compute the edit distance function for ${\\rm Forb}(H)$, where $H$ is any so-called split graph, and the graph $H_9$, a graph first used to describe the difficulties in computing the edit distance function.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-05-10T18:25:57.000Z",
      "comment": "21 pages, 2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-09-27T20:18:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C80"
    ],
    "keywords": [
      "edit distance function",
      "hereditary property",
      "computation",
      "maximum normalized distance",
      "edge sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.3716M"
    }
  }
}