FINDING EVEN CYCLES EVEN FASTER

Authors
YUSTER R ZWICK U
Citation
R. Yuster et U. Zwick, FINDING EVEN CYCLES EVEN FASTER, SIAM journal on discrete mathematics, 10(2), 1997, pp. 209-222
Citations number
11
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
10
Issue
2
Year of publication
1997
Pages
209 - 222
Database
ISI
SICI code
0895-4801(1997)10:2<209:FECEF>2.0.ZU;2-9
Abstract
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k greater t han or equal to 2, there is an O(V-2) time algorithm that decides whet her an undirected graph G = (V, E) contains a simple cycle of length 2 k, and finds one if it does. (ii) There is an O(V-2) time algorithm th at finds a shortest even cycle in an undirected graph G = (V, E).