• On the generation of bicliques...

Result: On the generation of bicliques of a graph

Title:
On the generation of bicliques of a graph
Authors:
DIAS, Vania M. F, DE FIGUEIREDO, Celina M. H, SZWARCFITER, Jayme L
Source:
3rd Cologne/Twente Workshop on Graphs and Combinatorial OptimizationDiscrete applied mathematics. 155(14):1826-1832
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 16 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Recherche information. Graphe, Information retrieval. Graph, Addition, Adicción, Algorithme, Algorithm, Algoritmo, Combinatoire, Combinatorics, Combinatoria, Ensemble indépendant, Independent set, Conjunto independiente, Enumération, Enumeration, Enumeración, Graphe biparti, Bipartite graph, Grafo bipartido, Graphe complet, Complete graph, Grafo completo, Génération, Generation, Generación, Informatique théorique, Computer theory, Informática teórica, Optimisation, Optimization, Optimización, Temps polynomial, Polynomial time, Tiempo polinomial, Temps retard, Delay time, Tiempo retardo, 68R10, 68Wxx, Algorithms, Biclique, Convex bipartite graphs, NP-complete, Polynomial time delay
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
COPPE, Universidade Fédéral do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, Brazil
IM and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, Brazil
IM, COPPE, and NCE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, 21945-970 Rio de Janeiro, Brazil
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19046563
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.19046563
Database:
PASCAL Archive

Further Information

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B = X U Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X, Y ≠ Ø, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.