Exact Exponential-Time Algorithms for Finding Bicliques in a Graph

Henning Fernau; Serge Gaspers; Dieter Kratsch; Mathieu Liedloff; Daniel Raible

Retour

Acte de colloque

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph

Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff et Daniel Raible

8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.205-209

CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization (Paris, France, 02/06/2009)

2009

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.

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: Exact Exponential-Time Algorithms for Finding Bicliques in a Graph
Créateurs - sans rôle: Henning Fernau - Trèves (France)
Serge Gaspers - Algorithmes, Graphes et Combinatoire
Dieter Kratsch - Laboratoire d'Informatique Théorique et Appliquée
Mathieu Liedloff - Laboratoire d'Informatique Fondamentale d'Orléans
Daniel Raible - Trèves (France)
Détails de publication: 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.205-209
Colloque: CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization (Paris, France, 02/06/2009)
Identifiants: 9945953509311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-00400470