Bicolored independent sets and bicliques

We introduce the decision problem Bicolored Independent Set which generalizes the well-known NP-complete graph problem Independent Set. We present an O(1.2691n) time algorithm solving its counting analogue #Bicolored Independent Set. We show how to use this algorithm to establish algorithms solving...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2012-04, Vol.112 (8-9), p.329-334
Main Authors: Couturier, Jean-François, Kratsch, Dieter
Format: Article
Language:English
Subjects:
Algorithms
Analogue
Biclique
Computational Complexity
Computer Science
Counting
Decision theory
Exact exponential algorithms
Graph algorithms
Graph theory
Graphs
Independent set
Mathematical problems
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce the decision problem Bicolored Independent Set which generalizes the well-known NP-complete graph problem Independent Set. We present an O(1.2691n) time algorithm solving its counting analogue #Bicolored Independent Set. We show how to use this algorithm to establish algorithms solving biclique counting problems and provide an O(1.2691n) time algorithm solving #Bipartite Biclique and an O(1.6107n) time algorithm solving #Non-induced Biclique. ► NP-complete graph problems. ► Exact exponential time algorithms. ► Existence and counting problems. ► Bicolored independent sets. ► Bipartite bicliques and non-induced bicliques.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2012.01.010