Linear-time recognition of bipartite graphs plus two edges Export

@article{damaschke03, abstract = {Cai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time. We extend their result to bipartite graphs plus two edges. Our algorithm works on a depth-first-search spanning tree. This gives, as a byproduct, also a simplified solution to the one-edge case. It is a notoriously open question whether recognizing bipartite graphs plus k edges is a fixed-parameter tractable problem. The present result might support the affirmative conjecture.}, author = {Damaschke, Peter}, citeulike-article-id = {2648332}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0012-365X(02)00493-4}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V00-479KDP2-5/2/f82dd95cedb96643502da4395da35477}, day = {6}, doi = {10.1016/S0012-365X(02)00493-4}, journal = {Discrete Mathematics}, keywords = {algorithms, graphs, mathematics}, month = {February}, number = {1-3}, pages = {99--112}, posted-at = {2008-04-10 09:16:15}, priority = {2}, title = {Linear-time recognition of bipartite graphs plus two edges}, url = {http://dx.doi.org/10.1016/S0012-365X(02)00493-4}, volume = {262}, year = {2003} }

TY - JOUR ID - damaschke03 L3 - citeulike-article-id:2648332 N2 - Cai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time. We extend their result to bipartite graphs plus two edges. Our algorithm works on a depth-first-search spanning tree. This gives, as a byproduct, also a simplified solution to the one-edge case. It is a notoriously open question whether recognizing bipartite graphs plus k edges is a fixed-parameter tractable problem. The present result might support the affirmative conjecture. IS - 1-3 JF - Discrete Mathematics EP - 112 TI - Linear-time recognition of bipartite graphs plus two edges VL - 262 SP - 99 KW - algorithms KW - graphs KW - mathematics AU - Damaschke, Peter PY - 2003/02/06/ UR - http://dx.doi.org/10.1016/S0012-365X(02)00493-4 ER -