Show simple item record

AuthorVerbitsky, Olegdc.contributor.author
Date of accession2016-03-15T09:03:41Zdc.date.accessioned
Available in OPARU since2016-03-15T09:03:41Zdc.date.available
Year of creation1995dc.date.created
AbstractGiven 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.dc.description.abstract
Languageendc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
KeywordLargest common subgraph problemdc.subject
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHGraph theorydc.subject.lcsh
TitleOn the largest common subgraph problemdc.title
Resource typeArbeitspapierdc.type
DOIhttp://dx.doi.org/10.18725/OPARU-2441dc.identifier.doi
PPN1651678871dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-vts-81736dc.identifier.urn
GNDTeilgraphdc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften und Informatikuulm.affiliationGeneral
Date of activation2012-09-02T20:17:14Zuulm.freischaltungVTS
Peer reviewneinuulm.peerReview
Shelfmark print versionQAA 5/A4.95,1uulm.shelfmark
DCMI TypeTextuulm.typeDCMI
VTS-ID8173uulm.vtsID
CategoryPublikationenuulm.category
Ulm seriesUlmer Informatik-Berichteuulm.seriesUlmName
University Bibliographyjauulm.unibibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record