Finding odd cycle transversals

0.00 Avg rating—0 Votes

Article ID:	iaor20051033
Country:	Netherlands
Volume:	32
Issue:	4
Start Page Number:	299
End Page Number:	301
Publication Date:	Jul 2004
Journal:	Operations Research Letters
Authors:	Reed Bruce, Vetta Adrian, Smith Kaleigh
Keywords:	combinatorial analysis

Abstract:

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.

Reviews

Required fields are marked *. Your email address will not be published.