• English
    • Deutsch
View Item 
  •   OPARU Home
  • Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
  • Publikationen
  • View Item
  •   OPARU Home
  • Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
  • Publikationen
  • View Item
  • English 
    • English
    • Deutsch
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.

On the largest common subgraph problem

Thumbnail
Download
vts_8173_11975.pdf (924.9Kb)
18 S.
 
Veröffentlichung
2012-09-02
DOI
10.18725/OPARU-2441
Arbeitspapier


Authors
Verbitsky, Oleg
Faculties
Fakultät für Ingenieurwissenschaften und Informatik
Ulm serial
Ulmer Informatik-Berichte
License
Standard
https://oparu.uni-ulm.de/xmlui/license_v3
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 problem
Dewey Decimal Group
DDC 004 / Data processing & computer science

Metadata
Show full item record

Citation 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

Other citation formats



About OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsFacultiesInstitutionsPersonsResource typesUlm SerialsDewey Decimal ClassesFundingThis CollectionFacultiesInstitutionsPersonsResource typesUlm SerialsDewey Decimal ClassesFunding

My Account

LoginRegister

Statistics

View Usage Statistics

About OPARU | Contact Us
Impressum | Privacy statement