Javascript is not activated in your browser. This website needs javascript activated to work properly.
Du är här

Counting Closed Trails

Publiceringsår: 2013
Språk: Engelska
Sidor: 1-3
Publikation/Tidskrift/Serie: Information Processing Letters
Volym: 113
Nummer: 1-2
Dokumenttyp: Artikel
Förlag: Elsevier


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, [5], thus improving both upon the $O(1.66^n)$ time randomized algorithm for general graphs (Björklund, 2010,, [1]), as well as the $O(1.69^n)$ time deterministic algorithm for claw-free graphs by Broersma et al.



  • Mathematics and Statistics


  • Vetenskapsrådet
  • Exact algorithms
  • Algorithms
  • ISSN: 0020-0190

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen