An exact exponential time algorithm for counting bipartite cliques.

Konstantin Kutzkov

    Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-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.
    Original languageEnglish
    JournalInformation Processing Letters
    Volume112
    Issue number13
    Pages (from-to)535-539
    Number of pages5
    ISSN0020-0190
    Publication statusPublished - 2012

    Keywords

    • Analysis of algorithms; Exact exponential time algorithms; Counting bipartite cliques

    Fingerprint

    Dive into the research topics of 'An exact exponential time algorithm for counting bipartite cliques.'. Together they form a unique fingerprint.

    Cite this