|
|||||
|
|
Finding odd cycle transversals |
|
| Authors: | Bruce Reed Adrian Vetta |
| Affiliation: | a School of Computer Science, McGill University, Room 301, McConnell Engineering Building, 3480 University, Montreal, Québec, Canada H3A 2A7 b School of Computer Science, McGill University, Room 318, McConnell Engineering Building, 3480 University, Montreal, Québec, Canada H3A 2A7 c Department of Mathematics and Statistics and School of Computer Science, McGill University, Room 1118, Burnside Building, 805 Sherbrooke, Montreal, Québec, Canada H3A 2K6 |
| 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. |
| Keywords: | Odd cycle transversal Odd cycle packing Bipartite graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |