Algorithms for induced biclique optimization problems

作者: Fanica Gavril

DOI: 10.1016/J.IPL.2011.02.005

关键词: CographModular decompositionChordal graphCombinatoricsDiscrete mathematics1-planar graphSplit graphIndifference graphAlgorithmPathwidthPolygon-circle graphMathematics

摘要: We present polynomial time algorithms for induced biclique optimization problems in the following families of graphs: polygon-circle graphs, 4-hole-free complements interval-filament graphs and subtree-filament graphs. Such are to find maximum: bicliques, balanced bicliques edge bicliques. These have applications clustering proteins by PPI criteria, documents, web pages.

参考文章(24)
Alexandr Kostochka, Jan Kratochvíl, Covering and coloring polygon-circle graphs Discrete Mathematics. ,vol. 163, pp. 299- 305 ,(1997) , 10.1016/S0012-365X(96)00344-5
Fǎnicǎ Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs Journal of Combinatorial Theory, Series B. ,vol. 16, pp. 47- 56 ,(1974) , 10.1016/0095-8956(74)90094-X
Hung Xuan Ta, Liisa Holm, Evaluation of different domain-based methods in protein interaction prediction Biochemical and Biophysical Research Communications. ,vol. 390, pp. 357- 362 ,(2009) , 10.1016/J.BBRC.2009.09.130
Fanica Gavril, 3D-interval-filament graphs Discrete Applied Mathematics. ,vol. 155, pp. 2625- 2636 ,(2007) , 10.1016/J.DAM.2007.08.006
Jeremy P. Sinrad, Elaine M. Eschen, An O(n2 algorithm for circular-arc graph recognition symposium on discrete algorithms. pp. 128- 137 ,(1993) , 10.5555/313559.313637
Louigi Addario-Berry, Maria Chudnovsky, Frédéric Havet, Bruce Reed, Paul Seymour, Bisimplicial vertices in even-hole-free graphs Journal of Combinatorial Theory, Series B. ,vol. 98, pp. 1119- 1164 ,(2008) , 10.1016/J.JCTB.2007.12.006
Egon Balas, Chang Sung Yu, On graphs with polynomially solvable maximum‐weight clique problem Networks. ,vol. 19, pp. 247- 253 ,(1989) , 10.1002/NET.3230190206
Jessica Enright, Lorna Stewart, Subtree filament graphs are subtree overlap graphs Information Processing Letters. ,vol. 104, pp. 228- 232 ,(2007) , 10.1016/J.IPL.2007.07.004