271:
Maximum common induced subgraph algorithms form the basis for both graph differencing and graph alignment. Graph differencing identifies and highlights differences between two graphs by pinpointing changes, additions, or deletions. Graph alignment involves finding correspondences between the vertices
314:) are represented as graph data structures. Graph differencing can be used to detect changes between different versions of software code and models for change auditing, debugging, version control and collaborative team development.
357:
255:
may be mapped. Both versions of the McSplit algorithm outperform the clique encoding for many graph classes. A more efficient implementation of McSplit is McSplitDAL+PR, which combines a
177:
203:
448:
804:
144:
546:
Proceedings of the Twenty-Sixth
International Joint Conference on Artificial Intelligence, {IJCAI} 2017, Melbourne, Australia, August 19-25, 2017
506:
Principles and
Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings
597:
521:
399:
236:
can be used to find the maximum common induced subgraph. Moreover, a modified maximum-clique algorithm can be used to find a maximum common
563:
434:
366:
417:
303:
544:
McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2017), "A Partitioning
Algorithm for Maximum Common Subgraph Problems",
384:
STACS 92: 9th Annual
Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992, Proceedings
794:
247:
algorithm that does not use the clique encoding, but uses a compact data structure to keep track of the vertices in graph
328:
88:
21:
386:, Lecture Notes in Computer Science, vol. 577, Springer Science $ \mathplus$ Business Media, pp. 375–388,
615:"A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics"
311:
244:
209:
107:
799:
415:
Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number",
119:
114:
problem, the maximum common induced subgraph problem is also hard to approximate. This implies that, unless
111:
508:, Lecture Notes in Computer Science, vol. 9892, Springer International Publishing, pp. 350–368,
256:
221:
654:"Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review"
707:
149:
750:
182:
288:
731:
527:
440:
770:
723:
673:
634:
593:
559:
517:
430:
395:
362:
762:
715:
665:
626:
583:
578:
Calabrese, Andrea; Cardone, Lorenzo; Licata, Salvatore; Porro, Marco; Quer, Stefano (2023).
549:
509:
479:
422:
387:
352:
348:
56:
37:
653:
323:
292:
280:
123:
711:
693:"Maximum common subgraph isomorphism algorithms for the matching of chemical structures"
296:
276:
233:
129:
692:
788:
531:
483:
382:
Kann, Viggo (1992), "On the approximability of the maximum common subgraph problem",
284:
470:(1976), "Subgraph isomorphism, matching relational structures and maximal cliques",
735:
497:
McCreesh, Ciaran; Ndiaye, Samba Ndojh; Prosser, Patrick; Solnon, Christine (2016),
467:
444:
103:, so that this entire graph must appear as an induced subgraph of the other graph.
17:
580:
A Web
Scraping Algorithm to Improve the Computation of the Maximum Common Subgraph
513:
84:
499:"Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems"
498:
452:
766:
719:
630:
391:
774:
677:
638:
588:
554:
614:
426:
727:
307:
260:
755:
International
Journal of Pattern Recognition and Artificial Intelligence
115:
52:
582:. SCITEPRESS - Science and Technology Publications. pp. 197–206.
358:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
302:
The problem is also particularly useful in software engineering and
275:
Maximum common induced subgraph algorithms have a long tradition in
669:
613:
Schietgat, Leander; Ramon, Jan; Bruynooghe, Maurice (2013-12-01).
243:
The McSplit algorithm (along with its McSplit↓ variant) is a
146:-vertex graphs, always finds a solution within a factor of
272:
and edges of two graphs to identify similar structures.
751:"Thirty Years of Graph Matching in Pattern Recognition"
749:
Conte, D.; Foggia, P.; Sansone, C.; Vento, M. (2004).
208:
One possible solution for this problem is to build a
185:
152:
132:
306:, where software code and engineering models (e.g.,
224:
corresponds to a maximum common induced subgraph of
259:agent with some heuristic scores computed with the
197:
171:
138:
652:Ehrlich, Hans-Christian; Rarey, Matthias (2011).
619:Annals of Mathematics and Artificial Intelligence
95:equals the number of vertices in the smaller of
79:have a common induced subgraph with at least
48:, and that has as many vertices as possible.
8:
700:Journal of Computer-Aided Molecular Design
691:Raymond, John W.; Willett, Peter (2002),
587:
553:
184:
157:
151:
131:
418:Proc. 38th ACM Symp. Theory of Computing
87:. It is a generalization of the induced
340:
805:Computational problems in graph theory
234:algorithms for finding maximum cliques
658:WIREs Computational Molecular Science
7:
71:. The problem is to decide whether
14:
295:, code analysis, compilers, and
548:, ijcai.org, pp. 712–719,
304:model-based systems engineering
172:{\displaystyle n^{1-\epsilon }}
26:maximum common induced subgraph
472:Information Processing Letters
251:to which each vertex in graph
198:{\displaystyle \epsilon >0}
1:
220:. In this graph, the largest
514:10.1007/978-3-319-44953-1_23
484:10.1016/0020-0190(76)90049-1
329:Maximum common edge subgraph
89:subgraph isomorphism problem
22:theoretical computer science
821:
83:vertices. This problem is
59:, the input is two graphs
767:10.1142/S0218001404003228
631:10.1007/s10472-013-9335-0
392:10.1007/3-540-55210-3_198
108:hardness of approximation
589:10.5220/0012130800003538
720:10.1023/A:1021271615909
427:10.1145/1132516.1132612
120:approximation algorithm
112:maximum independent set
555:10.24963/ijcai.2017/99
257:Reinforcement Learning
199:
173:
140:
51:Finding this graph is
36:is a graph that is an
285:pharmacophore mapping
210:modular product graph
200:
174:
141:
795:NP-complete problems
421:, pp. 681–690,
183:
179:of optimal, for any
150:
130:
91:, which arises when
55:. In the associated
712:2002JCAMD..16..521R
372:A1.4: GT48, pg.202.
289:pattern recognition
195:
169:
136:
599:978-989-758-665-1
523:978-3-319-44952-4
401:978-3-540-55210-9
139:{\displaystyle n}
812:
779:
778:
746:
740:
738:
697:
688:
682:
681:
649:
643:
642:
610:
604:
603:
591:
575:
569:
568:
557:
541:
535:
534:
503:
494:
488:
486:
463:
457:
455:
412:
406:
404:
379:
373:
371:
361:, W.H. Freeman,
353:David S. Johnson
349:Michael R. Garey
345:
245:forward checking
204:
202:
201:
196:
178:
176:
175:
170:
168:
167:
145:
143:
142:
137:
110:results for the
57:decision problem
38:induced subgraph
820:
819:
815:
814:
813:
811:
810:
809:
800:Cheminformatics
785:
784:
783:
782:
748:
747:
743:
695:
690:
689:
685:
651:
650:
646:
612:
611:
607:
600:
577:
576:
572:
566:
543:
542:
538:
524:
501:
496:
495:
491:
465:
464:
460:
437:
414:
413:
409:
402:
381:
380:
376:
369:
347:
346:
342:
337:
324:Molecule mining
320:
293:computer vision
281:cheminformatics
269:
181:
180:
153:
148:
147:
128:
127:
124:polynomial time
12:
11:
5:
818:
816:
808:
807:
802:
797:
787:
786:
781:
780:
761:(3): 265–298.
741:
706:(7): 521–533,
683:
670:10.1002/wcms.5
644:
625:(4): 343–376.
605:
598:
570:
564:
536:
522:
489:
458:
435:
407:
400:
374:
367:
339:
338:
336:
333:
332:
331:
326:
319:
316:
297:model checking
277:bioinformatics
268:
265:
194:
191:
188:
166:
163:
160:
156:
135:
118:, there is no
28:of two graphs
13:
10:
9:
6:
4:
3:
2:
817:
806:
803:
801:
798:
796:
793:
792:
790:
776:
772:
768:
764:
760:
756:
752:
745:
742:
737:
733:
729:
725:
721:
717:
713:
709:
705:
701:
694:
687:
684:
679:
675:
671:
667:
663:
659:
655:
648:
645:
640:
636:
632:
628:
624:
620:
616:
609:
606:
601:
595:
590:
585:
581:
574:
571:
567:
565:9780999241103
561:
556:
551:
547:
540:
537:
533:
529:
525:
519:
515:
511:
507:
500:
493:
490:
485:
481:
477:
473:
469:
462:
459:
454:
450:
446:
442:
438:
436:1-59593-134-1
432:
428:
424:
420:
419:
411:
408:
403:
397:
393:
389:
385:
378:
375:
370:
368:0-7167-1045-5
364:
360:
359:
354:
350:
344:
341:
334:
330:
327:
325:
322:
321:
317:
315:
313:
309:
305:
300:
298:
294:
290:
286:
282:
278:
273:
266:
264:
262:
258:
254:
250:
246:
241:
239:
235:
232:. Therefore,
231:
227:
223:
219:
215:
211:
206:
192:
189:
186:
164:
161:
158:
154:
133:
125:
121:
117:
113:
109:
104:
102:
98:
94:
90:
86:
82:
78:
74:
70:
67:and a number
66:
62:
58:
54:
49:
47:
43:
39:
35:
31:
27:
23:
19:
758:
754:
744:
703:
699:
686:
664:(1): 68–79.
661:
657:
647:
622:
618:
608:
579:
573:
545:
539:
505:
492:
478:(4): 83–84,
475:
471:
468:Burstall, R.
466:Barrow, H.;
461:
416:
410:
383:
377:
356:
343:
312:UML diagrams
301:
274:
270:
267:Applications
252:
248:
242:
237:
229:
225:
217:
213:
207:
105:
100:
96:
92:
80:
76:
72:
68:
64:
60:
50:
45:
41:
33:
29:
25:
18:graph theory
15:
263:algorithm.
85:NP-complete
789:Categories
335:References
240:subgraph.
775:0218-0014
678:1759-0876
639:1573-7470
532:215812381
238:connected
187:ϵ
165:ϵ
162:−
122:that, in
106:Based on
728:12510884
453:TR05-100
355:(1979),
318:See also
308:Simulink
261:PageRank
40:of both
736:5202419
708:Bibcode
445:5713815
53:NP-hard
773:
734:
726:
676:
637:
596:
562:
530:
520:
451:
443:
433:
398:
365:
222:clique
116:P = NP
732:S2CID
696:(PDF)
528:S2CID
502:(PDF)
441:S2CID
771:ISSN
724:PMID
674:ISSN
635:ISSN
594:ISBN
560:ISBN
518:ISBN
449:ECCC
431:ISBN
396:ISBN
363:ISBN
351:and
228:and
216:and
190:>
99:and
75:and
63:and
44:and
32:and
24:, a
20:and
763:doi
716:doi
666:doi
627:doi
584:doi
550:doi
510:doi
480:doi
423:doi
388:doi
299:.
212:of
126:on
16:In
791::
769:.
759:18
757:.
753:.
730:,
722:,
714:,
704:16
702:,
698:,
672:.
660:.
656:.
633:.
623:69
621:.
617:.
592:.
558:,
526:,
516:,
504:,
474:,
447:,
439:,
429:,
394:,
310:,
291:,
287:,
283:,
279:,
205:.
777:.
765::
739:.
718::
710::
680:.
668::
662:1
641:.
629::
602:.
586::
552::
512::
487:.
482::
476:4
456:.
425::
405:.
390::
253:G
249:H
230:H
226:G
218:H
214:G
193:0
159:1
155:n
134:n
101:H
97:G
93:k
81:k
77:H
73:G
69:k
65:H
61:G
46:H
42:G
34:H
30:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.