On the computation of edit distance functions

DOI10.1016/j.disc.2014.09.005zbMath1303.05051arXiv1012.3716OpenAlexW2044256035MaRDI QIDQ472982

Ryan R. Martin

Publication date: 20 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.3716

zbMATH Keywords

symmetrizationsplit graphhereditary propertyedit distancecolored regularity graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The edit distance function of some graphs, A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity, On the edit distance of powers of cycles

Cites Work

• Unnamed Item
• Unnamed Item
• The edit distance function and symmetrization
• The maximum edit distance from hereditary graph properties
• Edit distance and its computation
• Hardness of edge-modification problems
• Bandwidth and density for block graphs
• Boundedness of optimal matrices in extremal multigraph and digraph problems
• On the Edit Distance from K2,t-Free Graphs
• On the editing distance of graphs
• What is the furthest graph from a hereditary property?
• Inertia sets for graphs on six or fewer vertices
• Stability‐type results for hereditary properties
• Avoiding Patterns in Matrices Via a Small Number of Changes