On the largest common subgraph problem
Arbeitspapier
Faculties
Fakultät für Ingenieurwissenschaften und InformatikUlm serial
Ulmer Informatik-Berichte
Abstract
Given two graphs G 1 = <V1, E1> and G 2 = <V2, E2>, |V 1I = IV 2| = n, to determine whether they have a size-k common subgraph is one of the earliest examples of an NP-complete problem (by a trivial reduction from the Maximum Clique problem). We show that this problem for equally sized G 1 and G 2, i.e. when IE 1I = IE 2I = m, remains NP-complete.
Date created
1995
Subject Headings
Teilgraph [GND]Graph theory [LCSH]
Keywords
Largest common subgraph problemDewey Decimal Group
DDC 004 / Data processing & computer scienceMetadata
Show full item recordCitation example
Verbitsky, Oleg (2012): On the largest common subgraph problem. Open Access Repositorium der Universität Ulm. http://dx.doi.org/10.18725/OPARU-2441