A Separator-based Algorithm for the Graph Edit Distance Problem

Lars M\"uller; Laura B\"ulte; Petra Mutzel; Philip Mayer

REVIEW 1 major objections 6 minor 18 references

A Separator-based Algorithm for the Graph Edit Distance Problem

T0 review · 1 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper presents SR-GED, a recursive separator-based algorithm that computes exact graph edit distance in $O^*((4+\epsilon)^n)$ time and polynomial space when one input graph admits strictly sublinear balanced separators, covering…

desk verdict Genuinely new separator-based exact GED algorithm with O*((4+ε)^n) on planar/minor-free/bounded-treewidth graphs; runtime proof currently has a fixable sign error in Lemma 19 that a referee must catch before publication. read the letter →

arxiv 2608.04583 v1 pith:WJANH2IV submitted 2026-08-05 cs.DS

Laura Bülte , Philip Mayer , Lars Müller , Petra Mutzel This is my paper · ORCID

classification cs.DS MSC 68Q2505C8568R1090C27

keywords GraphEditDistanceexactexponential-timealgorithmsbalancedseparatorsplanargraphsminor-freetreewidthTravelingSalesmanProblemQuadraticAssignment

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that exact graph edit distance (GED) between two $n$-node graphs can be computed in $O^*((4+\epsilon)^n)$ time and polynomial space whenever one of the two graphs belongs to a hereditary graph class, closed under taking induced subgraphs, that admits strictly sublinear balanced separators. Such classes include planar graphs, graphs excluding a fixed $K_h$ minor, and graphs of bounded treewidth, so the result replaces the brute-force $O^*(n!)$ worst-case bound for exact GED on these classes. The algorithm also returns an optimal node mapping and edit sequence, and the same runtime bound carries over to the traveling salesman problem and to quadratic assignment problems with a suitably separable nonzero-flow graph. The paper further observes that the result cannot extend to arbitrary graphs unless the exponential time hypothesis fails.

What carries the argument

The load-bearing mechanism is the pair consisting of a balanced separator and adapted node edit costs. A balanced $\alpha$-separator is a vertex set whose removal leaves two parts of size at most $\alpha n$; the named graph classes supply such separators at every induced subgraph. Adapted node edit costs add the cost of the cut edges between a remaining vertex and the already-fixed separator image to that vertex's substitution cost, so the two sides of the recursion no longer interact through the cut. Lemma 15 turns this into the decomposition $\mathrm{GED}(G_1\cup G_2,H)=\min_{W_1}(\mathrm{GED}(G_1,H[W_1])+\mathrm{GED}(G_2,H-W_1)+c^+_\delta(W_1))$, where the last term is the insertion cost for edges crossing the image cut in $H$, and this is what makes independent recursive calls possible. The runtime analysis multiplies the separator-enumeration factor $n^{s(n)}$ against the bipartition-branching factor $2^n$ at every level; the condition $s(n)=o(n/\log^2 n)$ keeps the cumulative product at $2^{o(n)}$, giving the base $4$.

What would settle it

One direct check: for a candidate graph class, compute the size of the smallest balanced separator of every induced subgraph along the recursion tree of SR-GED. A single graph whose induced subgraph at size $m$ requires a balanced separator of size $\Omega(m/\log m)$ would place that graph outside Corollary 22, and an instance family where the total separator size along a root-to-leaf path is $\Omega(n/\log n)$ rather than $o(n/\log n)$ would make the exponent in Theorem 18 larger than $\log_2(4+\epsilon)n$, refuting the $(4+\epsilon)^n$ claim for that family.

Watch

Extended reading notes

Core claim

The central discovery is that separator-based divide-and-conquer can solve GED exactly despite the need to match two graphs at once. At each recursive step the algorithm picks a small balanced separator $S$ in the 'easy' graph $G$, enumerates every injective image of $S$ in the other graph $H$, and rewrites the node edit costs so that the costs of editing edges crossing the separator cut are charged to the remaining vertices. Once $S$ is removed, $G$ splits into two disconnected pieces; by enumerating all bipartitions of $H$'s remaining vertices into the two image sets, the two pieces become independent subproblems. The paper proves this recursion is exact and shows that when the separator size is $s(n)=o(n/\log^2 n)$, the total work is $O^*((4+\epsilon)^n)$ after rebalancing the separators.

Load-bearing premise

The load-bearing premise is that every induced subgraph of the separable input graph that the recursion produces has a balanced separator of size $s(m)=o(m/\log^2 m)$; if any recursive subproblem lacks such a separator, the product bound in the runtime proof stops being $2^{o(n)}$ and the $(4+\epsilon)^n$ guarantee is not established.

Editorial extensions

If this is right

Exact GED and an optimal node map can be computed in $O^*((4+\epsilon)^n)$ time and polynomial space for planar graphs, $K_h$-minor-free graphs, and hereditary bounded-treewidth graph classes.
The same bound applies to the traveling salesman problem, matching the known $O^*(4^n)$ polynomial-space bound up to the $\epsilon$.
Quadratic assignment instances with symmetric distances and a nonzero-flow interaction graph that is $(\alpha, O(n^{1-\delta}))$-balanced-separable inherit the same runtime.
Because the argument needs the separator structure in only one of the two input graphs, the improvement is available whenever either graph of a GED instance is planar, minor-free, or low-treewidth.
The recursive structure allows SR-GED to be combined with practical exact solvers such as ILP-based or $A^*$-based methods at the leaves of the recursion.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The adapted-cost decomposition is a template for other injective-mapping optimization problems, not just GED: any objective that can be written as node costs plus edge costs over a bijection should admit the same separator recursion.
The constant 4 comes from the product of separator enumeration and bipartition enumeration; pruning bipartitions with labels or degree statistics, or trading memory for time with dynamic programming, may lower the base in practice and possibly in theory.
When comparing two real-world graphs, the algorithm's asymmetry suggests always routing the recursion through the graph with better separator structure, which could be decided by a quick treewidth or separator heuristic.
The reported low treewidths of GEDLIB benchmarks indicate that, once engineered, this worst-case improvement may translate into exact solutions on much larger instances than current tree-search or ILP solvers handle, though that extrapolation is an empirical hope rather than a theorem of the paper.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth a serious look. It gives the first exact algorithm for GED with a c^n worst-case bound on planar, K_h-minor-free, and bounded-treewidth classes, achieving O*((4+ε)^n) in polynomial space. The separator recursion with adapted node edit costs (Definition 9) and the cut-cost decomposition (Lemma 15) are genuinely new, and the correctness induction is clean. The runtime analysis up to the point of Lemma 19 is coherent, and the external separator theorems are cited correctly.

The main problem is that Lemma 19 as written is wrong. With β∈(0,1), log_β(1/ε) is negative, so the claimed separator-size increase c = 2^{⌈log_β(1/ε)⌉} is less than 1. The correct expression is 2^{⌈log_{1/β}(1/ε)⌉} (equivalently, the recursion depth is ⌈log_β(ε)⌉). This is a typo rather than a conceptual gap—the intended rebalancing argument is clear and the asymptotic result survives after replacing the constant—but as written, Theorem 20's proof is invalid. A referee should require this fix.

Two minor issues: adapted node edit costs are computed in O(|S| n^2), not O(n^2) as claimed in the proof of Theorem 18; this is still polynomial, so the O* bound is unaffected. The TSP reduction (Theorem 27) is terse; I believe it works because deleting a cycle edge is made prohibitively expensive, but the text should spell out why non-edges in the target graph do not create zero-cost shortcuts.

This is a final-style paper for researchers in exact exponential algorithms, especially for GED, TSP, and QAP. It is a serious contribution with a plausible, novel result. I would send it to peer review rather than desk-reject, with an explicit note to the referees to verify the constants in Lemmas 19 and Theorem 20.

Referee Report

1 major / 6 minor

Summary. The paper proposes SR-GED, a recursive exact algorithm for the Graph Edit Distance (GED) on undirected labeled graphs with equal numbers of vertices. At each recursive step the algorithm computes a balanced separator S in one input graph G, enumerates all injective images of S in H, adapts the node edit costs to absorb the cut costs between S and the remaining graph, and then splits the remaining graph into two independent subproblems by enumerating all bipartitions of the remaining vertices of H. The paper proves correctness by an induction using Lemma 11, Corollary 13, and Lemma 15, and analyzes the running time for hereditary graph classes with balanced separators, claiming O^*((4+ε)^n) time and polynomial space when the separator size is o(n/log^2 n), with applications to planar, K_h-minor-free, bounded-treewidth, TSP, and QAP instances.

Significance. If the runtime claim holds, the main result is a substantial improvement over the trivial O(n!) enumeration for exact GED on several important graph classes, and the authors argue it is the first worst-case c^n algorithm for these classes. The recursive decomposition with adapted node edit costs is clean, and the correctness argument is well structured. The paper also gives concrete applications to TSP and a class of QAP instances. However, the runtime proof contains a sign error in the logarithmic expression in Lemma 19 and Theorem 20 that makes the currently stated separator-size amplification false; the intended argument is easily repaired and the asymptotic claim is likely salvageable, but the formal proof as written is incomplete.

major comments (1)

[Section 4.2, Lemma 19 and Theorem 20] Lemma 19 defines c = 2^{ceil(log_β(1/ε))} with β∈(0,1) and ε∈(0,1/2), which makes the exponent negative and c<1. The proof's level count l := ceil(log_β(1/ε)) is negative, so the claimed α-separator of size at most c·s(n) is not established; indeed, rebalancing from a β-separator to a more balanced α=1/2+ε separator cannot shrink the separator. The correct depth is ceil(log_{1/β}(1/ε)) (equivalently ceil(log_β ε)), giving c>1. The same sign error propagates to the constant c_μ in Theorem 20, which should be 2^{ceil(log_{1/β}(1/μ))} (or 2^{ceil(log_β μ)}). Because Lemma 19 is the step that converts (β,s)-separability into (α,c·s)-separability, the proof of the O*((4+ε)^n) bound is incomplete as written; the intended conclusion survives after the correction, since the corrected c_μ is a fixed constant for fixed ε and β.

minor comments (6)

[Abstract and Theorem 20] The runtime in the abstract should be written O^*((4+ε)^n), not O^*(4+ε)^n, and the definition of c_μ in Theorem 20 lacks the braces around log_β(1/μ).
[Section 4.2, proof of Theorem 18] The text says a call 'enumerates (n_i choose s(n_i))' separator embeddings, but the algorithm enumerates injective maps from S into V(H), whose number is n_i!/(n_i-s(n_i))!; the bound ≤ n_i^{s(n_i)} used later is still valid.
[Section 2] The statement that the ETH lower bound n^{o(n)} is 'essentially the asymptotic runtime of a brute-force approach' is imprecise, since n^{o(n)} is much smaller than n!.
[Lemma 19 proof] The sentence 'the tree has at most l levels, giving a total of c≤2l nodes' should read c≤2^l, and the level count should be ceil(log_{1/β}(1/ε)) as discussed in the major comment.
[Definition 17 and Theorem 18] Definition 17 allows α∈(0,1), while Theorem 18 and Lemma 19 use α∈[1/2,1); the parameter ranges should be made consistent.
[Abstract and Theorem 20] The phrase 'strictly sublinear balanced separators' in the abstract is informal; the formal hypothesis in Theorem 20 is s(n)=o(n/log^2 n), which is not identical to the O(n^{1-ε}) definition given in Section 3.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the runtime and correctness derivations rest on the GED definition, explicit cost decompositions, and external separator theorems, not on self-referential assumptions or fitted parameters.

full rationale

The paper's central claim, that SR-GED computes exact GED in O*((4+eps)^n) time on hereditary separator-admitting classes, is derived from independent ingredients. Correctness follows from Definition 4 (GED as a minimum over bijections), Lemma 8 (exact decomposition of edit costs), Lemma 11 (restricted GED reduction), Lemma 15 (combining disjoint subgraphs), and an induction in Theorem 16. Each of these is a mathematical identity or induction over the recursion; none assumes the target runtime. The runtime bound in Theorem 18 is a recurrence whose two factors are the branching over separator embeddings and bipartitions, using only the definition of an (alpha,s)-balanced-separable graph. The subsequent applications rely on external separator theorems: Lipton-Tarjan for planar graphs, Alon-Seymour-Thomas for K_h-minor-free graphs, and Robertson-Seymour for bounded treewidth. These are cited as established external results, not as self-citations, and they do not contain the GED runtime claim. The only self-adjacent citation is to the authors' prior ILP work [17], used as background on practical approaches, not as load-bearing support for the new result. The GEDLIB treewidth measurements in Appendix C are empirical observations, not fitted parameters renamed as predictions. One mathematical issue does exist: Lemma 19 and Theorem 20 contain a sign/level-count error in the expression log_beta(1/eps), which should be log_beta(eps), making the constant c<1 as written; however, this is a correctness and proof-completeness defect, not circular reasoning. It does not reduce the claim to its inputs. Therefore the paper shows no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; epsilon and the separator size functions come from external graph theory. The only inputs from prior literature are standard separator theorems and the metric-cost equivalence, neither of which contains the target runtime result.

assumptions (4)

standard math External separator theorems guarantee (alpha,s)-balanced separators for planar, K_h-minor-free, and bounded-treewidth hereditary graph classes (Theorems 23-25)
Invoked in Section 5 to instantiate the separator condition that drives the runtime bound.
domain assumption The node-map formulation of GED is equivalent to the edit-sequence formulation when costs are metric; non-metric costs can be preprocessed by a metric closure (Appendix A, citing [9])
Justifies restricting to bijective node maps and equal-size graphs; the paper supplies a preprocessing argument.
domain assumption The graph class is hereditary, so every induced subgraph arising in recursion remains in the class and has a separator of the guaranteed size (Corollary 22)
Used in the recursion and in the runtime product over levels; without it the separator size bound could fail on subproblems.
standard math Knapsack-style partition of connected components into two balanced groups is solvable in polynomial time (Section 4.2, runtime item 1)
Needed to find the balanced bipartition V1,V2 of G-S; standard pseudo-polynomial DP since component sizes sum to at most n.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Separator-based Algorithm for the Graph Edit Distance Problem." pith.science (2026). https://pith.science/paper/WJANH2IV

@misc{pith2026260804583,
  author       = {Pith},
  title        = {Pith review of: A Separator-based Algorithm for the Graph Edit Distance Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJANH2IV}},
  note         = {Machine review of arXiv:2608.04583}
}

abstract

The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 13 canonical work pages

[1]

A graph database repository and performance evaluation metrics for graph edit distance

1 Zeina Abu-Aisheh, Romain Raveaux, and Jean-Yves Ramel. A graph database repository and performance evaluation metrics for graph edit distance. InGraph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15,

work page 2015
[3]

3 TatsuyaAkutsu, TakeyukiTamura, DaijiFukagawa, andAtsuhiroTakasu

doi:10.5220/0005209202710278. 3 TatsuyaAkutsu, TakeyukiTamura, DaijiFukagawa, andAtsuhiroTakasu. Efficientexponential- time algorithms for edit distance between unordered trees.Journal of Discrete Algorithms, 25:79–93,

work page doi:10.5220/0005209202710278
[10]

16 Marek Cygan, Fedor V

doi: 10.1016/j.knosys.2018.10.002. 16 Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight lower bounds on graph embedding problems.J. ACM, 64(3):18:1–18:22, 2017.doi:10.1145/3051094. 17 Andrea D’Ascenzo, Julian Meffert, Petra Mutzel, and Fabrizio Rossi. Enhancing graph edit dist...

arXiv 2018
[13]

29 Seyed Mehdi Lajevardi, Arathi Arakala, Stephen A

doi:10.1049/iet-bmt.2013.0086. 29 Seyed Mehdi Lajevardi, Arathi Arakala, Stephen A. Davis, and Kathy J. Horadam. Retina verificationsystembasedonbiometricgraphmatching.IEEE Transactions on Image Processing, 22(9):3625–3635, 2013.doi:10.1109/TIP.2013.2266257. XX:16 A Separator-based Algorithm for the Graph Edit Distance Problem 30 Eugene L. Lawler. The qua...

arXiv 2013
[18]

edges (m), and the maximum treewidth of any graph inG

We record for each datasetG the number of graphs |G|, the average number of nodes (n) resp. edges (m), and the maximum treewidth of any graph inG. As can be seen, all datasets consist of graphs with treewidths bounded by small constants. Dataset|G|max.navg.navg.mmax. treewidth AIDS-EDIT 2214 33 32.0 33 2 AIDS 2000 95 15.7 16 3 CMU-GED 111 30 30.0 79 7 GRE...

work page
[1962]

24 Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach

doi:10.1137/0110015. 24 Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach. GEDEVO: An evolu- tionary graph edit distance algorithm for biological network alignment. InGerman Conference on Bioinformatics 2013, volume 34 ofOpen Access Series in Informatics (OASIcs), pages 68–79. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2013.doi:10.42...

doi:10.1137/0110015 2013
[1990]

5 Afrouz Jabal Ameli, Jesper Nederlof, and Shengzhe Wang

doi:10.1090/ S0894-0347-1990-1065053-0. 5 Afrouz Jabal Ameli, Jesper Nederlof, and Shengzhe Wang. Improved space-time tradeoffs for permutation problems via extremal combinatorics,

work page 1990
[1994]

33 Richard J

doi:10.1007/3-540-58325-4\_168. 33 Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.doi:10.1137/0136016. 34 Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. InStructural, Syntactic, and Statistical ...

doi:10.1007/3-540-58325-4 1979

Show all 18 references

[2007]

36 Neil Robertson and P.D Seymour

URL: http://mlg07.dsi.unifi.it/pdf/ 02_Riesen.pdf. 36 Neil Robertson and P.D Seymour. Graph minors. II. algorithmic aspects of tree-width.Journal of Algorithms, 7(3):309–322, 1986.doi:10.1016/0196-6774(86)90023-4. 37 Alberto Sanfeliu and King-Sun Fu. A distance measure between...

1986
[2008]

Springer, 2008.doi: 10.1007/978-3-540-89689-0\_33

Proceedings, Lecture Notes in Computer Science, pages 287–297. Springer, 2008.doi: 10.1007/978-3-540-89689-0\_33. 35 Kaspar Riesen, Stefan Fankhauser, and Horst Bunke. Speeding up graph edit distance computation with a bipartite heuristic. InMining and Learning with Graphs, ML...

2008 doi
[2013]

doi:10.1145/2430553.2430557. 11 H. Bunke. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8):689–694, 1997.doi:10.1016/S0167-8655(97)00060-3. 12 Horst Bunke. Error-tolerant graph matching: A formal framework and algorithms...

1997
[2014]

4 Noga Alon, Paul Seymour, and Robin Thomas

23rd Annual Symposium on Combinatorial Pattern Matching.doi:10.1016/ j.jda.2013.09.001. 4 Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808,

2013
[2015]

Springer, 2015.doi:10.1007/978-3-319-18224-7\_14

Proceedings, Lecture Notes in Computer Science, pages 138–147. Springer, 2015.doi:10.1007/978-3-319-18224-7\_14. 2 Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau. An exact graph edit distance algorithm for solving pattern recognition problems. In4th I...

2015 doi
[2017]

39 Hisao Tamaki

doi:10.1007/978-3-319-58961-9\_22. 39 Hisao Tamaki. Computing treewidth via exact and heuristic lists of minimal separators. In Analysis of Experimental Algorithms - Special Event, SEA 2 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers, Lecture Notes in Comput...

2019
[2019]

9 David B

doi: 10.48550/arXiv.1908.00265. 9 David B. Blumenthal and Johann Gamper. On the exact computation of the graph edit distance. Pattern Recognition Letters, 134:46–57,

1908 doi arXiv
[2020]

10 Martial Bourquin, Andy King, and Edward Robbins

Applications of Graph-based Techniques to Pattern Recognition.doi:10.1016/j.patrec.2018.05.002. 10 Martial Bourquin, Andy King, and Edward Robbins. BinSlayer: accurate comparison of binary executables. InProceedings of the 2nd ACM SIGPLAN Program Protection and Reverse Enginee...

2018 doi
[2022]

19 Carlos Garcia-Hernandez, Alberto Fernández, and Francesc Serratosa

doi:10.1007/978-3-031-21534-6\_5. 19 Carlos Garcia-Hernandez, Alberto Fernández, and Francesc Serratosa. Ligand-based virtual screening using graph edit distance as molecular similarity measure.Journal of Chemical Information and Modeling, 59(4):1410–1421, 2019.doi:10.1021/acs...
[2026]

6 Philip Bille

URL:https://arxiv.org/abs/ 2604.05661,arXiv:2604.05661. 6 Philip Bille. A survey on tree edit distance and related problems.Theoretical Computer Science, 337(1):217–239, 2005.doi:10.1016/j.tcs.2004.12.030. 7 David Blumenthal, Sébastien Bougleux, Luc Brun, and Johann Gamper. GE...

2005 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

A graph database repository and performance evaluation metrics for graph edit distance

1 Zeina Abu-Aisheh, Romain Raveaux, and Jean-Yves Ramel. A graph database repository and performance evaluation metrics for graph edit distance. InGraph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15,

work page 2015

[2] [3]

3 TatsuyaAkutsu, TakeyukiTamura, DaijiFukagawa, andAtsuhiroTakasu

doi:10.5220/0005209202710278. 3 TatsuyaAkutsu, TakeyukiTamura, DaijiFukagawa, andAtsuhiroTakasu. Efficientexponential- time algorithms for edit distance between unordered trees.Journal of Discrete Algorithms, 25:79–93,

work page doi:10.5220/0005209202710278

[3] [10]

16 Marek Cygan, Fedor V

doi: 10.1016/j.knosys.2018.10.002. 16 Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight lower bounds on graph embedding problems.J. ACM, 64(3):18:1–18:22, 2017.doi:10.1145/3051094. 17 Andrea D’Ascenzo, Julian Meffert, Petra Mutzel, and Fabrizio Rossi. Enhancing graph edit dist...

arXiv 2018

[4] [13]

29 Seyed Mehdi Lajevardi, Arathi Arakala, Stephen A

doi:10.1049/iet-bmt.2013.0086. 29 Seyed Mehdi Lajevardi, Arathi Arakala, Stephen A. Davis, and Kathy J. Horadam. Retina verificationsystembasedonbiometricgraphmatching.IEEE Transactions on Image Processing, 22(9):3625–3635, 2013.doi:10.1109/TIP.2013.2266257. XX:16 A Separator-based Algorithm for the Graph Edit Distance Problem 30 Eugene L. Lawler. The qua...

arXiv 2013

[5] [18]

edges (m), and the maximum treewidth of any graph inG

We record for each datasetG the number of graphs |G|, the average number of nodes (n) resp. edges (m), and the maximum treewidth of any graph inG. As can be seen, all datasets consist of graphs with treewidths bounded by small constants. Dataset|G|max.navg.navg.mmax. treewidth AIDS-EDIT 2214 33 32.0 33 2 AIDS 2000 95 15.7 16 3 CMU-GED 111 30 30.0 79 7 GRE...

work page

[6] [1962]

24 Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach

doi:10.1137/0110015. 24 Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach. GEDEVO: An evolu- tionary graph edit distance algorithm for biological network alignment. InGerman Conference on Bioinformatics 2013, volume 34 ofOpen Access Series in Informatics (OASIcs), pages 68–79. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2013.doi:10.42...

doi:10.1137/0110015 2013

[7] [1990]

5 Afrouz Jabal Ameli, Jesper Nederlof, and Shengzhe Wang

doi:10.1090/ S0894-0347-1990-1065053-0. 5 Afrouz Jabal Ameli, Jesper Nederlof, and Shengzhe Wang. Improved space-time tradeoffs for permutation problems via extremal combinatorics,

work page 1990

[8] [1994]

33 Richard J

doi:10.1007/3-540-58325-4\_168. 33 Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.doi:10.1137/0136016. 34 Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. InStructural, Syntactic, and Statistical ...

doi:10.1007/3-540-58325-4 1979