Searching the maximum bicliques or bipartite subgraphs in a graph is a tough question. We proposed a new and efficient method, Searching Quasi-Bicliques (SQB) algorithm, to detect maximum quasi-bicliques from protein-...Searching the maximum bicliques or bipartite subgraphs in a graph is a tough question. We proposed a new and efficient method, Searching Quasi-Bicliques (SQB) algorithm, to detect maximum quasi-bicliques from protein-protein interaction network. As a Divide-and-Conquer method, SQB consists of three steps: first, it divides the protein-protein interaction network into a number of Distance-2-Subgraphs;second, by combining top-down and branch-and-bound methods, SQB seeks quasi-bicliques from every Distance-2-Subgraph;third, all the redundant results are removed. We successfully applied our method on the Saccharomyces cerevisiae dataset and obtained 2754 distinct quasi-bicliques.展开更多
We develop improved approximation algorithms for two NP-hard problems:the dense-n/2-subgraph and table compression.Based on SDP relaxation and advanced rounding techniques,we first propose 0.5982 and 0.5970-approximat...We develop improved approximation algorithms for two NP-hard problems:the dense-n/2-subgraph and table compression.Based on SDP relaxation and advanced rounding techniques,we first propose 0.5982 and 0.5970-approximation algorithms respec-tively for the dense-n/2-subgraph problem(DSP)and the table compression problem(TCP).Then we improve these bounds to 0.6243 and 0.6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation.The results for TCP beat the 0.5 bound of a simple greedy algorithm on this problem,and hence answer an open question of Anderson in an affirmative way.展开更多
文摘Searching the maximum bicliques or bipartite subgraphs in a graph is a tough question. We proposed a new and efficient method, Searching Quasi-Bicliques (SQB) algorithm, to detect maximum quasi-bicliques from protein-protein interaction network. As a Divide-and-Conquer method, SQB consists of three steps: first, it divides the protein-protein interaction network into a number of Distance-2-Subgraphs;second, by combining top-down and branch-and-bound methods, SQB seeks quasi-bicliques from every Distance-2-Subgraph;third, all the redundant results are removed. We successfully applied our method on the Saccharomyces cerevisiae dataset and obtained 2754 distinct quasi-bicliques.
基金supported by NNSF of China(Grant Nos.10401038&10171108)Startup grant for doctoral research of Beijing University of Technology+1 种基金The second author's work was supported by NNSF of China(Grant Nos.10271002&70271014)The third author's work was supported by NSERC(Grant No.10004901)
文摘We develop improved approximation algorithms for two NP-hard problems:the dense-n/2-subgraph and table compression.Based on SDP relaxation and advanced rounding techniques,we first propose 0.5982 and 0.5970-approximation algorithms respec-tively for the dense-n/2-subgraph problem(DSP)and the table compression problem(TCP).Then we improve these bounds to 0.6243 and 0.6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation.The results for TCP beat the 0.5 bound of a simple greedy algorithm on this problem,and hence answer an open question of Anderson in an affirmative way.
