# An attractive class of bipartite graphs

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 293-301
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRodica Boliac, and Vadim Lozin. "An attractive class of bipartite graphs." Discussiones Mathematicae Graph Theory 21.2 (2001): 293-301. <http://eudml.org/doc/270378>.

@article{RodicaBoliac2001,

abstract = {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.},

author = {Rodica Boliac, Vadim Lozin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {bipartite graphs; structural characterization; polynomial algorithm; polynomial-time algorithms},

language = {eng},

number = {2},

pages = {293-301},

title = {An attractive class of bipartite graphs},

url = {http://eudml.org/doc/270378},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Rodica Boliac

AU - Vadim Lozin

TI - An attractive class of bipartite graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 293

EP - 301

AB - 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.

LA - eng

KW - bipartite graphs; structural characterization; polynomial algorithm; polynomial-time algorithms

UR - http://eudml.org/doc/270378

ER -

## References

top- [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). Zbl0931.05078
- [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₇. Zbl0756.68084
- [3] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F. Zbl0687.05033
- [4] G. Chaty and M. Chein, Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Mathematica 16 (1979) 183-187. Zbl0446.05037
- [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. Zbl0953.05510
- [6] G. Fricke and R. Laskar, Strong matchings on trees, Congr. Numer 89 (1992) 239-243. Zbl0786.05065
- [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.
- [8] A. Kötzig, Paare Hajös the Graphen, Casopis Pest. Mat. 88 (1963) 236-241.
- [9] H. Müller, Alternating cycle free matchings in chordal bipartite graphs, Order 7 (1990) 11-21, doi: 10.1007/BF00383169. Zbl0805.68091
- [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. Zbl0622.06002
- [11] M. Zito, Linear time maximum induced matching algorithm for trees, Nordic J. Computing 7 (2000) 58-63. Zbl0957.68095

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.