Finding odd cycle transversals

详细信息	查看全文 | 推荐本文 |

• 作者：Reed ; Bruce ; Smith ; Kaleigh ; Vetta ; Adrian
• 关键词：Odd cycle transversal ; Odd cycle packing ; Bipartite graph
• 刊名：Operations Research Letters
• 出版年：2004
• 期刊代码：134_01676377
• 类别：et
• 出版时间：July, 2004
• 卷：32
• 期：4
• 页码：299-301
• 文件大小：160 K

摘要

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.