MENENTUKAN SUBGRAF BICLIQUE MAKSIMAL DENGAN PASANGAN POLA TERTUTUP DARI MATRIKS ADJACENCY
Keywords:
Subgraf biclique maksimal, Pasangan pola tertutup, Matriks adjacency
Abstract
Subgraf biclique maksimal, sering juga disebut sebagai subgraf bipartisi komplit maksimal dapat dimodelkan ke banyak aplikasi dari banyak bidang ilmu. Dari hubungan antara subgraf biclique maksimal dengan pola tertutup dari suatu matriks adjacency pada graf tidak berarah dan tanpa lup G diperoleh : (1). Banyak pola tertutup pada matriks adjacency G adalah genap; dan (2). Banyak dari pola tertutup adalah tepat dua kali banyak subgraf biclique maksimal dari G. Dilakukan juga perbandingan hasil dari proses pencarian maksimal biclique subgraf dengan pola tertutup pada matriks adjacency dengan hasil yang dilakukan dengan algoritma konsensus.
References
Agrawal. R, Imielinski .T, dan Swami .A(1993)Mining Association Rules between Sets of Items in Large Databases Proceedings of the 1993 ACM-IGMOD international Conference onManagement of Data. 207-216.
Alexe.G, Alexe.S, Crama .Y, Foldes. S, P. L. Hammer, and B. Simeone(2004), Consensus algorithms for the generation of all maximal bicliques. Discrete Applied Mathematics 145(1), pp. 11-21.
Asratian A. S, Tristan M. J. Denley and Roland Haggkvist (1998) ”Bipartite Graphs and Their Application”, Cambridge Tracts inMathematics 131.
Bondy J. A. and U. S. R. Murty (1982) Graph Theory with Applications. NorthHolland. Brualdi R.A and Herbert J. Ryser,(1991) ”Combinatorial Matrix Theory”,
Encyclopedia of Mathematics and its applications, Cambridge Univ. Press, Cambridge, UK.
Cornaz D(2007). The maximum induced bipartite subgraph problem with edge weights. SIAM J. Discrete Math 21(3), 662–675.
Cornaz D and Jean Fonlupt(2006) Chromatic characterization of biclique cover Discrete Mathematics 306(5), 495-507
Dawande.M, Pinar Keskinocak, Jayashankar M. Swaminathan and Sridhar Tayur (2001) On Bipartite and Multipartite Clique Problems. Journal Of Algorithms 41,388-403
Enver Kayaaslan (2010) On Enumerating All Maximal Biclique of Bipartite Graphs CTW 2010
Eppstein D (1994). Arboricity and bipartite subgraph listing algorithms. Information Processing Letters 51:207–211.
Godsil C and Gordon Royle (2000)Algebraic Graph Theory. Graduate Texts in Mathematics 207. Springer.
Haemers Willem H(2001) Biclique and Eigen values Journal of Combinatorial Theory Series B 82, 56-66
Hochbaum Dorit S (1998). Approximating Clique and Biclique problems. Journal of algorithms, 29,174–200.
Li. J,HaiquanLi,Donny Soh, danLimsoonWong (2005)Acorrespondence between maksimal complite bipartite subgraph and closed pattern Knowledge Discovery in
Databases;PKDD 2005 Lecture Notes in Computer Science 3721, 146-156
Liu G , Kelvin Sim, Jinyan Li (2006) Efficient Mining of Large Maximal Bicliques. Data Warehousing and knowledge discovery. Lecture Notes in Computer Science, 4081: 437–448.
Liu Y, Aixin Sun, Han T Loh, Wen F Lu and Ee-Peng Lim (2008). Advances of Computational Intelegence in Industrial Systems. Studies in Computational Intelligence Vol 116: 99–116.
Lowell W. Beineke, Robin J. Wilson and Peter J. Cameron(2004) Topics In Algebraic Graph Theory. Cambridge University Press.
Marcus Daniel A. (2008). ”Graf Theory. A Problem Oriented Approach”, The Mathematical Association of America. (Incorporated)
Vania M.F. Dias, Celine M.H. de Figueiredo and Jayme L. Szwarcfiter. (2007). On the generation of bicliques of a graph. Discrete Applied Mathematics, 155(2007) : 1826-1832.
Yan. X and Jiawei Han (2003) Closed Graph: Mining Closed Frequent Graph Pattern. Conference on Knowledge discovery and data mining 286-295.
Yang Xiang, Philip R.O. Payne, and Kun Huang (2012) Transactional Database Transformation and Its Application in Prioritizing Human Disease Genes IEEE/ACM Trans Comput Biol Bioinform 9(1) :294-304.
Alexe.G, Alexe.S, Crama .Y, Foldes. S, P. L. Hammer, and B. Simeone(2004), Consensus algorithms for the generation of all maximal bicliques. Discrete Applied Mathematics 145(1), pp. 11-21.
Asratian A. S, Tristan M. J. Denley and Roland Haggkvist (1998) ”Bipartite Graphs and Their Application”, Cambridge Tracts inMathematics 131.
Bondy J. A. and U. S. R. Murty (1982) Graph Theory with Applications. NorthHolland. Brualdi R.A and Herbert J. Ryser,(1991) ”Combinatorial Matrix Theory”,
Encyclopedia of Mathematics and its applications, Cambridge Univ. Press, Cambridge, UK.
Cornaz D(2007). The maximum induced bipartite subgraph problem with edge weights. SIAM J. Discrete Math 21(3), 662–675.
Cornaz D and Jean Fonlupt(2006) Chromatic characterization of biclique cover Discrete Mathematics 306(5), 495-507
Dawande.M, Pinar Keskinocak, Jayashankar M. Swaminathan and Sridhar Tayur (2001) On Bipartite and Multipartite Clique Problems. Journal Of Algorithms 41,388-403
Enver Kayaaslan (2010) On Enumerating All Maximal Biclique of Bipartite Graphs CTW 2010
Eppstein D (1994). Arboricity and bipartite subgraph listing algorithms. Information Processing Letters 51:207–211.
Godsil C and Gordon Royle (2000)Algebraic Graph Theory. Graduate Texts in Mathematics 207. Springer.
Haemers Willem H(2001) Biclique and Eigen values Journal of Combinatorial Theory Series B 82, 56-66
Hochbaum Dorit S (1998). Approximating Clique and Biclique problems. Journal of algorithms, 29,174–200.
Li. J,HaiquanLi,Donny Soh, danLimsoonWong (2005)Acorrespondence between maksimal complite bipartite subgraph and closed pattern Knowledge Discovery in
Databases;PKDD 2005 Lecture Notes in Computer Science 3721, 146-156
Liu G , Kelvin Sim, Jinyan Li (2006) Efficient Mining of Large Maximal Bicliques. Data Warehousing and knowledge discovery. Lecture Notes in Computer Science, 4081: 437–448.
Liu Y, Aixin Sun, Han T Loh, Wen F Lu and Ee-Peng Lim (2008). Advances of Computational Intelegence in Industrial Systems. Studies in Computational Intelligence Vol 116: 99–116.
Lowell W. Beineke, Robin J. Wilson and Peter J. Cameron(2004) Topics In Algebraic Graph Theory. Cambridge University Press.
Marcus Daniel A. (2008). ”Graf Theory. A Problem Oriented Approach”, The Mathematical Association of America. (Incorporated)
Vania M.F. Dias, Celine M.H. de Figueiredo and Jayme L. Szwarcfiter. (2007). On the generation of bicliques of a graph. Discrete Applied Mathematics, 155(2007) : 1826-1832.
Yan. X and Jiawei Han (2003) Closed Graph: Mining Closed Frequent Graph Pattern. Conference on Knowledge discovery and data mining 286-295.
Yang Xiang, Philip R.O. Payne, and Kun Huang (2012) Transactional Database Transformation and Its Application in Prioritizing Human Disease Genes IEEE/ACM Trans Comput Biol Bioinform 9(1) :294-304.
Article Metrics
Abstract views: 83
pdf downloads: 509
Published
2014-10-31
How to Cite
Hutabarat, H. D. M. (2014). MENENTUKAN SUBGRAF BICLIQUE MAKSIMAL DENGAN PASANGAN POLA TERTUTUP DARI MATRIKS ADJACENCY. Numeracy, 1(2), 30-44. https://doi.org/10.46244/numeracy.v1i2.126
Issue
Section
Articles
