Exact Exponential-Time Algorithms for Finding Bicliques in a Graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph

Henning Fernau
  • Function : Author
  • PersonId : 857693
Trier University
Serge Gaspers
  • Function : Author
  • PersonId : 936216
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
  • Function : Author
  • PersonId : 857696
Trier University

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.

Domains

Data Structures and Algorithms [cs.DS] Discrete Mathematics [cs.DM]

Serge Gaspers  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00400470

Submitted on : Tuesday, June 30, 2009-6:50:24 PM

Last modification on : Friday, March 24, 2023-2:52:52 PM

No file

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00400470 , version 1

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS UNIV-ORLEANS MSL MSL-THESE ALGCO LIRMM UNIV-LORRAINE TDS-MACS MIPS UNIV-MONTPELLIER
436 View
0 Download

Share

More