A balanced bipartite graph is a bipartite graph (U,V,E) such that |U|=|V|. Balanced bipartite subgraphs problems arise in such fields as VLSI design and flexible manufaturing. An example is the following: given a graph G and a positive integer m, does G contain a balanced complete bipartite subgraph with at least 2m vertices? This problem is NP-complete for several classes of graphs, including bipartite. We contribute to characterize "easy" classes and individuate properties useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced P5 on the basis of a result of Bacsò and Tuza. We generalize the result to particular subclasses of (i) graphs wth no odd cycles of given size, (ii) paw-free graphs, (iii)diamndo-free graphs.
Polynomial Algorithms for Special Cases of the Balanced Bipartite Subgraph Problem
ARBIB, CLAUDIO;
1999-01-01
Abstract
A balanced bipartite graph is a bipartite graph (U,V,E) such that |U|=|V|. Balanced bipartite subgraphs problems arise in such fields as VLSI design and flexible manufaturing. An example is the following: given a graph G and a positive integer m, does G contain a balanced complete bipartite subgraph with at least 2m vertices? This problem is NP-complete for several classes of graphs, including bipartite. We contribute to characterize "easy" classes and individuate properties useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced P5 on the basis of a result of Bacsò and Tuza. We generalize the result to particular subclasses of (i) graphs wth no odd cycles of given size, (ii) paw-free graphs, (iii)diamndo-free graphs.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
