Skip to search box Skip to navigation Skip to main content

An exact exponential time algorithm for counting bipartite cliques.

Konstantin Kutzkov

Research Output:

Journal Article or Conference Article in Journal

Journal article

Research

Peer-review

Abstract

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n vertices. We achieve running time of O(1.249^n), improving upon known exact algorithms for finding and counting bipartite cliques.

Publication Information

Output type

Research Output:

Journal Article or Conference Article in Journal

Journal article

Research

Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 535-539 (5 pages)

Journal (Volume, Issue Number)

Information Processing Letters (Volume 112, Issue 13)

Publication milestones

Published - 2012

Publication status

Published - 2012

ISSN

0020-0190

Publication IDs

Scopus: 84859637684

Publication metrics

PlumX

Captures

6

Citation count

5