EVEN DIRECTED CYCLES IN H-FREE DIGRAPHS

Authors
GALLUCCIO A LOEBL M
Citation
A. Galluccio et M. Loebl, EVEN DIRECTED CYCLES IN H-FREE DIGRAPHS, Journal of algorithms, 27(1), 1998, pp. 26-41
Citations number
16
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
27
Issue
1
Year of publication
1998
Pages
26 - 41
Database
ISI
SICI code
0196-6774(1998)27:1<26:EDCIHD>2.0.ZU;2-J
Abstract
A digraph is H-free if its underlying graph does not contain a subgrap h contractible to the graph H. We provide a polynomial-time algorithm to solve the even cycle problem in the class of K-3,K-3-free digraphs and in the class of K-5-free digraphs. We also discuss the important r ole played bg the subdivisions of K-3,K-3 in solving the even cycle pr oblem in its generality. (C) 1998 Academic Press.