Exact Exponential-Time Algorithms for Finding Bicliques in a Graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph

Henning Fernau
  • Fonction : Auteur
  • PersonId : 857693
Serge Gaspers
  • Fonction : Auteur
  • PersonId : 936216
Daniel Raible
  • Fonction : Auteur
  • PersonId : 857696

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-00400470 , version 1 (30-06-2009)

Identifiants

  • HAL Id : lirmm-00400470 , version 1

Citer

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⟩
433 Consultations
0 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More