A digraph is H-free if its underlying graph does not contain a subgraph 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 role played bg the subdivisions of K-3,K-3 in solving the even cycle problem in its generality.
Even directed cycles in H-free digraphs
Galluccio A;
1998
Abstract
A digraph is H-free if its underlying graph does not contain a subgraph 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 role played bg the subdivisions of K-3,K-3 in solving the even cycle problem in its generality.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
