A correspondence between maximal complete bipartite subgraphs and closed patterns

Jinyan Li, Haiquan Li, Donny Soh, Limsoon Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

For an undirected graph G without self-loop, we prove: (i) that the number of closed patterns in the adjacency matrix of G is even; (ii) that the number of the closed patterns is precisely double the number of maximal complete bipartite subgraphs of G; (iii) that for every maximal complete bipartite subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, we can enumerate all maximal complete bipartite subgraphs by using efficient algorithms for mining closed patterns which have been extensively studied in the data mining field.

Original languageEnglish (US)
Title of host publicationKnowledge Discovery in Databases
Subtitle of host publicationPKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings
PublisherSpringer-Verlag
Pages146-156
Number of pages11
ISBN (Print)3540292446, 9783540292449
DOIs
StatePublished - 2005
Externally publishedYes
Event9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005 - Porto, Portugal
Duration: Oct 3 2005Oct 7 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3721 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005
Country/TerritoryPortugal
CityPorto
Period10/3/0510/7/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'A correspondence between maximal complete bipartite subgraphs and closed patterns'. Together they form a unique fingerprint.

Cite this