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.

Probably Optimal Graph Motifs

Författare

  • Andreas Björklund
  • Petteri Kaski
  • Lukasz Kowalik

Redaktör

  • Natacha Portier
  • Thomas Wilke

Summary, in English

We show an O^*(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute, and Min-Add. Moreover, we provide a piece of evidence that our result might be essentially tight: the existence of an O^*((2-epsilon)^k)-time algorithm for the Graph Motif problem implies an ((2-epsilon')^n)-time algorithm for Set Cover.

Publiceringsår

2013

Språk

Engelska

Sidor

20-31

Publikation/Tidskrift/Serie

[Host publication title missing]

Volym

20

Dokumenttyp

Konferensbidrag

Förlag

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Ämne

  • Computer Science

Conference name

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs

Conference date

2013-02-28

Status

Published

Projekt

  • Exact algorithms

Forskningsgrupp

  • Algorithms

ISBN/ISSN/Övrigt

  • ISSN: 1868-8969