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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.