Skip to Main content Skip to Navigation
Conference papers

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph

Abstract : We show that, given a graph G on n vertices, deciding if G has a complete bipartite subgraph with k_1 vertices in one part and k_2 vertices in the other part of its bipartition can be done in time O(1.8899^n) and polynomial space and in time O(1.8458^n) and exponential space.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00400470
Contributor : Serge Gaspers <>
Submitted on : Tuesday, June 30, 2009 - 6:50:24 PM
Last modification on : Thursday, January 17, 2019 - 3:06:04 PM

Identifiers

  • HAL Id : lirmm-00400470, version 1

Citation

Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Daniel Raible. Exact Exponential-Time Algorithms for Finding Bicliques in a Graph. CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Jun 2009, Paris, France. pp.205-209. ⟨lirmm-00400470⟩

Share

Metrics

Record views

778