Maximum Weighted Edge Biclique Problem on Bipartite Graphs

Autor:	Arti Pandey, Gopika Sharma, Nivedit Jain
Rok vydání:	2020
Předmět:	Combinatorics Mathematics::Combinatorics Computer Science::Discrete Mathematics Bipartite permutation graphs Bipartite graph Graph algorithms Complete bipartite graph Graph MathematicsofComputing_DISCRETEMATHEMATICS Real number Mathematics
Zdroj:	Algorithms and Discrete Applied Mathematics ISBN: 9783030392185 CALDAM
Popis:	For a graph G, a complete bipartite subgraph of G is called a biclique of G. For a weighted graph \(G=(V,E,w)\), where each edge \(e\in E\) has a weight \(w(e)\in \mathbb {R}\), the Maximum Weighted Edge Biclique (MWEB) problem is to find a biclique H of G such that \(\sum _{e\in E(H)}w(e)\) is maximum. The decision version of the MWEB problem is known to be NP-complete for bipartite graphs. In this paper, we show that the decision version of the MWEB problem remains NP-complete even if the input graph is a complete bipartite graph. On the positive side, if the weight of each edge is a positive real number in the input graph G, then we show that the MWEB problem is \(O(n^2)\)-time solvable for bipartite permutation graphs, and \(O(m+n)\)-time solvable for chain graphs, which is a subclass of bipartite permutation graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::9ba14deb3505db575b5d7f0fc1ad9ab0 https://doi.org/10.1007/978-3-030-39219-2_10 Zobrazit plný text záznamu