Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A biclique is a maximal bipartite complete induced subgraph of G. Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, bounds on the maximum number of bicliques were given. In this paper we study bounds on the minimun number of bicliques of a graph. Since adding false-twin vertices to G does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques for a subclass of {C4,false-twin}-free graphs and for the class of {K3,false-twin}-free graphs. Finally we discuss the problem for general graphs. © 2016 Elsevier B.V.

Registro:

Documento: Artículo
Título:Tight lower bounds on the number of bicliques in false-twin-free graphs
Autor:Groshaus, M.; Montero, L.
Filiación:Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Laboratoire de Recherche en Informatique, Université Paris-Sud, Orsay CEDEX, France
Palabras clave:Bicliques; False-twin-free graphs; Lower bounds; Computational methods; Computer science; Biclique; Bicliques; Free graphs; General graph; Induced subgraphs; Lower bounds; Twin-free; Graphic methods
Año:2016
Volumen:636
Página de inicio:77
Página de fin:84
DOI: http://dx.doi.org/10.1016/j.tcs.2016.05.027
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v636_n_p77_Groshaus

Referencias:

  • Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B., Consensus algorithms for the generation of all maximal bicliques (2004) Discrete Appl. Math., 145 (1), pp. 11-21
  • Amilhastre, J., Vilarem, M.C., Janssen, P., Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs (1998) Discrete Appl. Math., 86 (2–3), pp. 125-144
  • Baker, E.J., Jay, J.J., Philip, V.M., Zhang, Y., Li, Z., Kirova, R., Langston, M.A., Chesler, E.J., Ontological discovery environment: a system for integrating gene–phenotype associations (2009) Genomics, 94 (6), pp. 377-387
  • Cheng, Y., Church, G.M., Biclustering of expression data (2000) Proc. Int. Conf. Intell. Syst. Mol. Biol., 8, pp. 93-103
  • Chesler, E.J., Langston, M.A., Combinatorial genetic regulatory network analysis tools for high throughput transcriptomic data (2007) Proceedings of the 2005 Joint Annual Satellite Conference on Systems Biology and Regulatory Genomics, RECOMB'05, pp. 150-165. , Springer-Verlag Berlin, Heidelberg
  • Damaschke, P., Enumerating maximal bicliques in bipartite graphs with favorable degree sequences (2014) Inform. Process. Lett., 114 (6), pp. 317-321
  • Dias, V.M.F., de Figueiredo, C.M.H., Szwarcfiter, J.L., Generating bicliques of a graph in lexicographic order (2005) Theoret. Comput. Sci., 337 (1–3), pp. 240-248
  • Eppstein, D., Arboricity and bipartite subgraph listing algorithms (1994) Inform. Process. Lett., 51 (4), pp. 207-211
  • Ganter, B., Wille, R., Formal Concept Analysis (1999), Springer-Verlag Berlin; Gaspers, S., Kratsch, D., Liedloff, M., On independent sets and bicliques in graphs (2008) Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., 5344, pp. 171-182. , Springer Berlin, Heidelberg
  • Gély, A., Nourine, L., Sadi, B., Enumeration aspects of maximal cliques and bicliques (2009) Discrete Appl. Math., 157 (7), pp. 1447-1459
  • Groshaus, M., Montero, L., Tight lower bounds on the number of bicliques in false-twin-free graphs (2015) Electron. Notes Discrete Math., 50, pp. 293-298. , LAGOS'15—VIII Latin-American Algorithms, Graphs and Optimization Symposium
  • Groshaus, M., Montero, L., On the iterated biclique operator (2013) J. Graph Theory, 73 (2), pp. 181-190
  • Habib, M., de Montgolfier, F., Paul, C., A simple linear-time modular decomposition algorithm for graphs, using order extension (2004) Algorithm Theory—SWAT 2004, Lecture Notes in Comput. Sci., 3111, pp. 187-198. , Springer Berlin
  • Kirova, R., Langston, M.A., Peng, X., Perkins, A.D., Chesler, E.J., A systems genetic analysis of chronic fatigue syndrome: combinatorial data integration from SNPs to differential diagnosis of disease (2006) Proceedings, International Conference for the Critical Assessment of Microarray Data Analysis, CAMDA06
  • Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A., Trawling the web for emerging cyber-communities (1999) Comput. Netw., 31 (11–16), pp. 1481-1493
  • Lehmann, S., Schwartz, M., Hansen, L.K., Biclique communities (2008) Phys. Rev. E (3), 78 (1). , 016108
  • Liu, J., Wang, W., Op-cluster: clustering by tendency in high dimensional space (2003) Third IEEE International Conference on Data Mining, 2003, ICDM 2003, pp. 187-194. , IEEE
  • Makino, K., Uno, T., New algorithms for enumerating all maximal cliques (2004) Algorithm Theory—SWAT 2004, Lecture Notes in Comput. Sci., 3111, pp. 260-272. , Springer Berlin
  • Mukherjee, A.P., Tirthapura, S., Enumerating maximal bicliques from a large graph using MapReduce (2014), http://arxiv.org/abs/1404.4910, CoRR; Mushlin, R.A., Kershenbaum, A., Gallagher, S.T., Rebbeck, T.R., A graph-theoretical approach for pattern discovery in epidemiological research (2007) IBM Syst. J., 46 (1), pp. 135-149
  • Prisner, E., Bicliques in graphs I: bounds on their number (2000) Combinatorica, 20 (1), pp. 109-117
  • Sanderson, M.J., Driskell, A.C., Ree, R.H., Eulenstein, O., Langley, S., Obtaining maximal concatenated phylogenetic data sets from large sequence databases (2003) Mol. Biol. Evol., 20 (7), pp. 1036-1042
  • Savio, M.R.D., Sankar, A., Vijayarajan, N.R., A novel enumeration strategy of maximal bicliques from 3-dimensional symmetric adjacency matrix (2014) Internat. J. Artif. Intell., 12 (2)
  • Schweiger, R., Linial, M., Linial, N., Generative probabilistic models for protein–protein interaction networks—the biclique perspective (2011) Bioinformatics, 27 (13), pp. i142-i148
  • Tanay, A., Sharan, R., Shamir, R., Discovering statistically significant biclusters in gene expression data (2002) Bioinformatics, 18 (suppl 1), pp. S136-S144
  • Wang, H., Wang, W., Yang, J., Yu, P.S., Clustering by pattern similarity in large data sets (2002) Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 394-405. , ACM
  • Xiang, Y., Payne, P., Huang, K., Transactional database transformation and its application in prioritizing human disease genes (2012) IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (1), pp. 294-304
  • Zaki, M.J., Ogihara, M., Theoretical foundations of association rules (1998) 3rd ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 71-78. , Citeseer
  • Zhang, Y., Phillips, C.A., Rogers, G.L., Baker, E.J., Chesler, E.J., Langston, M.A., On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types (2014) BMC Bioinformatics, 15, p. 110

Citas:

---------- APA ----------
Groshaus, M. & Montero, L. (2016) . Tight lower bounds on the number of bicliques in false-twin-free graphs. Theoretical Computer Science, 636, 77-84.
http://dx.doi.org/10.1016/j.tcs.2016.05.027
---------- CHICAGO ----------
Groshaus, M., Montero, L. "Tight lower bounds on the number of bicliques in false-twin-free graphs" . Theoretical Computer Science 636 (2016) : 77-84.
http://dx.doi.org/10.1016/j.tcs.2016.05.027
---------- MLA ----------
Groshaus, M., Montero, L. "Tight lower bounds on the number of bicliques in false-twin-free graphs" . Theoretical Computer Science, vol. 636, 2016, pp. 77-84.
http://dx.doi.org/10.1016/j.tcs.2016.05.027
---------- VANCOUVER ----------
Groshaus, M., Montero, L. Tight lower bounds on the number of bicliques in false-twin-free graphs. Theor Comput Sci. 2016;636:77-84.
http://dx.doi.org/10.1016/j.tcs.2016.05.027