Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Unique subgraphs are not easier to find

In English

Författare

Summary, in English

Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G isomorphic to H are sought.

Publiceringsår

2013

Språk

Engelska

Sidor

1247-1253

Publikation/Tidskrift/Serie

International Journal of Computer Mathematics

Volym

90

Issue

6

Dokumenttyp

Artikel i tidskrift

Förlag

Taylor & Francis

Ämne

  • Computer Science

Nyckelord

  • time complexity
  • induced subgraph isomorphism
  • isomorphism
  • unique subgraph occurrence
  • graph algorithms
  • subgraph

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1029-0265