Maximum Weighted Edge Biclique Problem on Bipartite Graphs
Maximum Weighted Edge Biclique Problem on Bipartite Graphs
复制标题
DOI：
10.1007/978-3-030-39219-2_10
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Arti Pandey;Gopika Sharma;N. Jain
中科院分区：
文献类型：
--
作者：
Arti Pandey;Gopika Sharma;N. Jain
对于图g，它的完全二部子图称为g的二次曲线。对于一个加权图，其中每条边都有一个权值，最大加权边Biclique（MWEB）问题是找到一个最大的双曲线。对于二部图，MWEB问题的决策版本已知是np完全的。在本文中，我们证明了即使输入图是完全二部图，MWEB问题的决策版本仍然是np完全的。在正方面，如果输入图g中每条边的权值是一个正实数，那么我们证明了MWEB问题对于二部置换图是时间可解的，对于二部置换图的一个子类链图是时间可解的。
For a graphG, a complete bipartite subgraph ofGis called a biclique ofG. For a weighted graph, where each edgehas a weight, theMaximum Weighted Edge Biclique(MWEB) problem is to find a bicliqueHofGsuch thatis 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 graphG, then we show that the MWEB problem is-time solvable for bipartite permutation graphs, and-time solvable for chain graphs, which is a subclass of bipartite permutation graphs.