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.

Counting Closed Trails

In English

Författare

  • Andreas Björklund
  • Petteri Kaski

Summary, in English

A closed trail is a connected graph whose every vertex is incident to an even number of edges. We give a deterministic algorithm that in time $2^{m/2}poly(m,n)$ finds the number of closed trails in a given graph G with n vertices and m edges. Moreover, within the same time bound we can determine every possible vertex set of a closed trail in G, together with the associated number of closed trails. Our algorithm can be used to deterministically find the longest cycle in an n-vertex claw-free graph in time $2^{n/2}poly(m,n)$ via a framework presented by Broersma et al. (in press, http://dx.doi.org/10.1007/s00453-011-9576-4) [5], thus improving both upon the $O(1.66^n)$ time randomized algorithm for general graphs (Björklund, 2010, http://dx.doi.org/10.1109/FOCS.2010.24, [1]), as well as the $O(1.69^n)$ time deterministic algorithm for claw-free graphs by Broersma et al.

Publiceringsår

2013

Språk

Engelska

Sidor

1-3

Publikation/Tidskrift/Serie

Information Processing Letters

Volym

113

Issue

1-2

Dokumenttyp

Artikel i tidskrift

Förlag

Elsevier

Ämne

  • Computer Science

Status

Published

Projekt

  • Exact algorithms

Forskningsgrupp

  • Algorithms

ISBN/ISSN/Övrigt

  • ISSN: 0020-0190