SwePub
Sök i SwePub databas

  Extended search

Träfflista för sökning "id:"swepub:oai:lup.lub.lu.se:aad66a56-1c56-4c71-9fa2-6be963c80266" "

Search: id:"swepub:oai:lup.lub.lu.se:aad66a56-1c56-4c71-9fa2-6be963c80266"

  • Result 1-1 of 1
Sort/group result
   
EnumerationReferenceCoverFind
1.
  • Björklund, Andreas, et al. (author)
  • Counting Closed Trails
  • 2013
  • In: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 113:1-2, s. 1-3
  • Journal article (peer-reviewed)abstract
    • 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.
  •  
Skapa referenser, mejla, bekava och länka
  • Result 1-1 of 1
Type of publication
journal article (1)
Type of content
peer-reviewed (1)
Author/Editor
Kaski, Petteri (1)
Björklund, Andreas (1)
University
Lund University (1)
Language
English (1)
Research subject (UKÄ/SCB)
Natural sciences (1)
Year
2013 (1)

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view