On the computation of edit distance functions

Details On the computation of edit distance functions On the computation of edit distance functions

2010-12-16

arxiv.org/abs/1012.3716v2

Mathematics

Combinatorics

21 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the computation of edit distance functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the computation of edit distance functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the computation of edit distance functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-220223