Abstract: The editing of a combinatorial object is the alteration of some of its elements such that the resulting object satisfies a certain fixed property. The edit problem for graphs, when the edges are added or deleted, was first studied independently by the authors and K'ezdy [J. Graph Theory (2008), 58(2), 123--138] and by Alon and Stav [Random Structures Algorithms (2008), 33(1), 87--104]. In this paper, a generalization of graph editing is considered for multicolorings of the complete graph as well as for directed graphs. Specifically, the number of edge-recolorings sufficient to be performed on any edge-colored complete graph to satisfy a given hereditary property is investigated. The theory for computing the edit distance is extended using random structures and so-called types or colored homomorphisms of graphs.
Recommendations
- Edit distance and its computation
- An edit distance between graph correspondences
- Approximating the geometric edit distance
- Approximating the geometric edit distance
- Distance edge-colourings and matchings
- A tunable distance measure for coloured solid models
- On the computation of edit distance functions
Cited in
(2)
This page was built for publication: Multicolor and directed edit distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q357457)
