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.
Type de document :
Communication dans un congrès
CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Jun 2009, Paris, France. 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.205-209, 2009, 〈http://www.lix.polytechnique.fr/ctw09/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00400470
Contributeur : Serge Gaspers <>
Soumis le : mardi 30 juin 2009 - 18:50:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • 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. 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.205-209, 2009, 〈http://www.lix.polytechnique.fr/ctw09/〉. 〈lirmm-00400470〉

Partager

Métriques

Consultations de la notice

467