Sequence to Graph Alignment

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs. The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983. A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning

Bounds Chart

Graph edit distance computationBoundsChart.png

Step Chart

Graph edit distance computationStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn