Publications in Scientific Journals:
S. Gaspers, D. Kratsch, M. Liedloff:
"On Independent Sets and Bicliques in Graphs";
Algorithmica,
Vol. 62
(2012),
No. 3-4;
637
- 658.
English abstract:
Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. In this paper we improve Prisnerīs upper bound on the number of maximal bicliques [Combinatorica, 2000] and show that the maximum number of maximal bicliques in a graph on n vertices is Θ(3n/3). Our major contribution is an exact exponential-time algorithm. This branching algorithm computes the number of distinct maximal independent sets in a graph in time O(1.3642n), where n is the number of vertices of the input graph. We use this counting algorithm and previously known algorithms for various other problems related to independent sets to derive algorithms for problems related to bicliques via polynomial-time reductions.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s00453-010-9474-1
Related Projects:
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.