
handle: 11564/135000
Summary: A balanced bipartite graph is a bipartite graph \((U,V,E)\) such that \(|U|=|V|\). Particular balanced bipartite subgraph problems have applications in fields such as VLSI design and flexible manufacturing. An example of such problems 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 graphs. However, the problem can be solved in polynomial time for particular graph classes. We aim to contribute to the characterization of ``easy'' classes of instances of the problem, and to individuate graph-theoretic properties that can be useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced \(P_5\) on the basis of a result of \textit{G. Bacsó} and \textit{Zs. Tuza} [Period. Math. Hung. 21, No. 4, 303-308 (1990; Zbl 0746.05065)]. We generalize the result to particular subclasses of (i) graphs with no odd cycles of given size, (ii) paw-free graphs, and (iii) diamond-free graphs.
balanced bipartite graph, subgraph problems, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, characterization, polynomial algorithm, NP-complete
balanced bipartite graph, subgraph problems, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, characterization, polynomial algorithm, NP-complete
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
