In a tri-partite biological network of transcription factors, their putative target genes, and the tissues in which the target genes are differentially expressed, a tightly inter-connected (dense) subgraph may reveal knowledge about tissue specific transcription regulation mediated by a specific set of transcription factors-a tissue-specific transcriptional module. This is just one context in which an efficient computation of dense subgraphs in a multi-partite graph is needed.