Open AccessAn attractive class of bipartite graphs
Author(s) -
Rodica Boliac,
Vadim Lozin
Publication year - 2001
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1151
Subject(s) - mathematics , bipartite graph , combinatorics , class (philosophy) , discrete mathematics , graph , computer science , artificial intelligence
In this paper we propose a structural characterization for a class ofbipartite graphs defined by two forbidden induced subgraphs. We show that theobtained characterization leads to polynomial-time algorithms for several problemsthat are NP-hard in general bipartite graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom