Counting Closed Trails
(2013) In Information Processing Letters 113(1-2). p.1-3- 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,... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3241135
- author
- Björklund, Andreas LU and Kaski, Petteri
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Information Processing Letters
- volume
- 113
- issue
- 1-2
- pages
- 1 - 3
- publisher
- Elsevier
- external identifiers
-
- wos:000312175200001
- scopus:84867744765
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2012.09.006
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- aad66a56-1c56-4c71-9fa2-6be963c80266 (old id 3241135)
- date added to LUP
- 2016-04-01 15:01:10
- date last changed
- 2022-01-28 03:37:42
@article{aad66a56-1c56-4c71-9fa2-6be963c80266,
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.}},
author = {{Björklund, Andreas and Kaski, Petteri}},
issn = {{0020-0190}},
language = {{eng}},
number = {{1-2}},
pages = {{1--3}},
publisher = {{Elsevier}},
series = {{Information Processing Letters}},
title = {{Counting Closed Trails}},
url = {{http://dx.doi.org/10.1016/j.ipl.2012.09.006}},
doi = {{10.1016/j.ipl.2012.09.006}},
volume = {{113}},
year = {{2013}},
}