##
This **preview** shows page *1-2-3-4-5-6-7-8-9-10-11-75-76-77-78-79-80-81-82-83-84-151-152-153-154-155-156-157-158-159-160-161*
out of 161 **pages**.

*View Full Document*

End of preview. Want to read all 161 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

String editingString editingString editingString editingString editingString editingString editingString editingString editingString editingString editingString editingString editingGraph editingGraph editingGraph editingGraph editingGraph editingGraph editingGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesGraph classesOriginal questionOriginal questionOriginal questionOriginal questionOriginal questionOriginal questionOriginal question``Forb''``Forb''``Forb''``Forb''``Forb''The big questionThe big questionThe big questionThe big questionThe big questionThe big questionThe big questionBipartite theoremBipartite theoremBipartite theoremBipartite theoremBipartite theoremBipartite theoremBipartite theoremThe real questionThe real questionThe real questionThe real questionThe real questionThe real questionPath on 4 verticesPath on 4 verticesPath on 4 verticesPath on 4 verticesAn obvious observationAn obvious observationAn obvious observationAn obvious observationAn obvious observationAn obvious observationCycle on 5 verticesCycle on 5 verticesCycle on 5 verticesAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmAn algorithmBut not for three partsBut not for three partsBut not for three partsBut not for three partsBut not for three partsBut not for three partsBut not for three partsBut not for three partsBut not for three partsThe result for $C_5$The result for $C_5$The result for $C_5$The result for $C_5$The result for $C_5$The result for $C_5$$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ facts$P_4$ lower bound$P_4$ lower bound$P_4$ lower bound$P_4$ lower bound$C_5$ facts$C_5$ facts$C_5$ facts$C_5$ facts$C_5$ facts$C_5$ lower bound$C_5$ lower bound$C_5$ lower bound$C_5$ lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundGeneralizing the lower boundAn exampleAn exampleAn exampleAn exampleAn exampleAn exampleAn exampleAn exampleThe lower boundThe lower boundThe lower boundThe lower boundThe lower boundUpper boundsUpper boundsUpper boundsComputing edit distanceComputing edit distanceComputing edit distanceComputing edit distanceComputing edit distanceWork to comeWork to comeWork to comeWork to comeWork to comeThanksThe edit distance in graphsRyan [email protected]eduMathematics Dept., Iowa State UAmes, Iowa 50010Joint work with:J´OZSEF BALOGH, UIUCMARIA AXENOVICH, IOWA STATE UANDR´E K´EZDY, LOUISVILLE UThe edit distance in graphs – p. 1/26String editingBiologists are concerned with DNA strings.The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAGGAGCTTAACTCTAGGTACA protein string.The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAGGAGCTTAACTCTAGGTACA protein string.Edit operations are:The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAGGAGCTCAACTCTAGGTACA protein string with a bit “flipped”.Edit operations are: flipping,The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAGGAGCTCAACTCTAGGTACA protein string with a bit “flipped”.Edit operations are: flipping,The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTAGGTACA protein string with a bit “inserted”.Edit operations are: flipping, inserting,The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTAGGTACA protein string with a bit “inserted”.Edit operations are: flipping, inserting,The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTAGGTACA protein string with a bit “inserted”.Edit operations are: flipping, inserting, and deleting.The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTGGTACA protein string with a bit “deleted”.Edit operations are: flipping, inserting, and deleting.The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTGGTACEdit operations are: flipping, inserting, and deleting.The edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTGGTACEdit operations are: flipping, inserting, and deleting.The edit distance between two stringsThe edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTGGTACEdit operations are: flipping, inserting, and deleting.The edit distance between two strings is the minimum number ofthese operationsThe edit distance in graphs – p. 2/26String editingBiologists are concerned with DNA strings.ACGGTAAGGAGCTCAACTCTGGTACEdit operations are: flipping, inserting, and deleting.The edit distance between two strings is the minimum number ofthese operations to get from one string to the other.The edit distance in graphs – p. 2/26Graph editingWe develop the same editing idea with graphs.The edit distance in graphs – p. 3/26Graph editingWe develop the same editing idea with graphs.A graph is an object with vertices.A graph.The edit distance in graphs – p. 3/26Graph editingWe develop the same editing idea with graphs.A graph is an object with vertices and edges.A graph.The edit distance in graphs – p. 3/26Graph editingWe develop the same editing idea with graphs.Begin with a graph on a fixed vertex set.A graph.The edit distance in graphs – p. 3/26Graph editingWe develop the same editing idea with graphs.Begin with a graph on a fixed vertex set.Editing of the graph.Edit it by deleting edges and adding edges.The edit distance in graphs – p. 3/26Graph editingWe develop the same editing idea with graphs.Begin with a graph on a fixed vertex set.Further editing of the graph.Edit it by deleting edges and adding edges.The edit distance in graphs – p. 3/26Graph classesThe editing of graphs to get from one graph to anotherThe edit distance in graphs – p. 4/26Graph classesThe editing of graphs to get from one graph to another is lessinteresting than getting from one graph to