PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 293-301
Tytuł artykułu

An attractive class of bipartite graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
21
Numer
2
Strony
293-301
Opis fizyczny
Daty
wydano
2001
otrzymano
2001-03-03
poprawiono
2001-05-19
Twórcy
  • RUTCOR, Rutgers University, 640 Bartholomew Rd. Piscataway NJ 08854-8003 USA
autor
  • RUTCOR, Rutgers University, 640 Bartholomew Rd. Piscataway NJ 08854-8003 USA
Bibliografia
  • [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).
  • [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₇.
  • [3] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F.
  • [4] G. Chaty and M. Chein, Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Mathematica 16 (1979) 183-187.
  • [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.
  • [6] G. Fricke and R. Laskar, Strong matchings on trees, Congr. Numer 89 (1992) 239-243.
  • [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.
  • [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.
  • [11] M. Zito, Linear time maximum induced matching algorithm for trees, Nordic J. Computing 7 (2000) 58-63.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1151
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.