An attractive class of bipartite graphs
Rodica Boliac ; Vadim Lozin
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 293-301 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270378 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1151,
     author = {Rodica Boliac and Vadim Lozin},
     title = {An attractive class of bipartite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {293-301},
     zbl = {1002.05060},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1151}
}

Rodica Boliac; Vadim Lozin. An attractive class of bipartite graphs. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 293-301. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1151/

[000] [1] V.E. Alekseev, A polynomial algorithm for finding maximum stable sets in fork-free graphs, Discrete Analysis and Operations Research, Ser.1, 6 (4) (1999) 3-19 (in Russian). | Zbl 0931.05078

[001] [2] A. Brandstädt, The jump number problem for biconvex graphs and rectangle covers of rectangular regions, Lecture Notes in Computer Science 380 (1989) 68-77, doi: 10.1007/3-540-51498-8₇. | Zbl 0756.68084

[002] [3] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F. | Zbl 0687.05033

[003] [4] G. Chaty and M. Chein, Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Mathematica 16 (1979) 183-187. | Zbl 0446.05037

[004] [5] E. Dahlhaus, The computation of the jump number of convex graphs, Lecture Notes in Computer Science 831 (1994) 176-185, doi: 10.1007/BFb0019434. | Zbl 0953.05510

[005] [6] G. Fricke and R. Laskar, Strong matchings on trees, Congr. Numer 89 (1992) 239-243. | Zbl 0786.05065

[006] [7] M.C. Golumbic and M. Lewenstein, New results on induced matchings, Discrete Appl. Math. 101 (2000) 157-165, doi: 10.1016/S0166-218X(99)00194-8.

[007] [8] A. Kötzig, Paare Hajös the Graphen, Casopis Pest. Mat. 88 (1963) 236-241.

[008] [9] H. Müller, Alternating cycle free matchings in chordal bipartite graphs, Order 7 (1990) 11-21, doi: 10.1007/BF00383169. | Zbl 0805.68091

[009] [10] G. Steiner and L. Stewart, A linear time algorithm to find the jump number of 2-dimensional bipartite orders, Order 3 (1987) 359-367, doi: 10.1007/BF00340778. | Zbl 0622.06002

[010] [11] M. Zito, Linear time maximum induced matching algorithm for trees, Nordic J. Computing 7 (2000) 58-63. | Zbl 0957.68095