An exact exponential time algorithm for counting bipartite cliques.

Konstantin Kutzkov

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.

Original language	English
Journal	Information Processing Letters
Volume	112
Issue number	13
Pages (from-to)	535-539
Number of pages	5
ISSN	0020-0190
Publication status	Published - 2012

Keywords

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

Cite this

@article{c19b38ce05144e4bb5adcf7fcb1004f5,

title = "An exact exponential time algorithm for counting bipartite cliques.",

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\textasciicircum{}n), improving upon known exact algorithms for finding and counting bipartite cliques.",

keywords = "Analysis of algorithms; Exact exponential time algorithms; Counting bipartite cliques, Analysis of algorithms; Exact exponential time algorithms; Counting bipartite cliques",

author = "Konstantin Kutzkov",

note = "@article\{DBLP:journals/ipl/Kutzkov12, author = \{Konstantin Kutzkov\}, title = \{An exact exponential time algorithm for counting bipartite cliques\}, journal = \{Inf. Process. Lett.\}, volume = \{112\}, number = \{13\}, year = \{2012\}, pages = \{535-539\}, ee = \{http://dx.doi.org/10.1016/j.ipl.2012.04.001\}, bibsource = \{DBLP, http://dblp.uni-trier.de\} \}",

year = "2012",

language = "English",

volume = "112",

pages = "535--539",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "13",

}

TY - JOUR

T1 - An exact exponential time algorithm for counting bipartite cliques.

AU - Kutzkov, Konstantin

N1 - @article{DBLP:journals/ipl/Kutzkov12, author = {Konstantin Kutzkov}, title = {An exact exponential time algorithm for counting bipartite cliques}, journal = {Inf. Process. Lett.}, volume = {112}, number = {13}, year = {2012}, pages = {535-539}, ee = {http://dx.doi.org/10.1016/j.ipl.2012.04.001}, bibsource = {DBLP, http://dblp.uni-trier.de} }

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Analysis of algorithms; Exact exponential time algorithms; Counting bipartite cliques

M3 - Journal article

SN - 0020-0190

VL - 112

SP - 535

EP - 539

JO - Information Processing Letters

JF - Information Processing Letters

IS - 13

ER -

An exact exponential time algorithm for counting bipartite cliques.

Abstract

Keywords

Fingerprint

Cite this