Linear-time recognition of bipartite graphs plus two edges

by: Peter Damaschke

Discrete Mathematics, Vol. 262, No. 1-3. (6 February 2003), pp. 99-112.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

zeichnendes

Find related articles with these CiteULike tags

algorithms, graphs, mathematics

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.

@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}, 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} }

RIS record

TY - JOUR ID - damaschke03 L3 - citeulike-article-id:2648332 TI - Linear-time recognition of bipartite graphs plus two edges JF - Discrete Mathematics VL - 262 IS - 1-3 SP - 99 EP - 112 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. 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 -

RIS BibTeX