Sökning: id:"swepub:oai:lup.lub.lu.se:aad66a56-1c56-4c71-9fa2-6be963c80266" >
Counting Closed Trails
Counting Closed Trails
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Kaski, Petteri (författare)
-
(creator_code:org_t)
- Elsevier BV, 2013
- 2013
- Engelska.
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 113:1-2, s. 1-3
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas