Generating bicliques of a graph in lexicographic order (Q557825): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Consensus algorithms for the generation of all maximal bicliques / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Absolute reflexive retracts and absolute bipartite retracts / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Bipartite and Multipartite Clique Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perfect Elimination and Chordal Bipartite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating Clique and Biclique Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On generating all maximal independent sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: On edge perfectness and classes of bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The maximum edge biclique problem is NP-complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4373687 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bicliques in graphs. I: Bounds on their number / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Algorithm for Generating All the Maximal Independent Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Node-and edge-deletion NP-complete problems / rank
 
Normal rank

Revision as of 12:07, 10 June 2024

scientific article
Language Label Description Also known as
English
Generating bicliques of a graph in lexicographic order
scientific article

    Statements

    Generating bicliques of a graph in lexicographic order (English)
    0 references
    30 June 2005
    0 references
    A complete bipartite set \(B\) of a graph is a subset of vertices admitting a bipartition \(B=X\cup 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\neq \emptyset\), then \(B\) is called proper. A biclique is a maximal proper complete bipartite set of a graph. The authors present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. They show also that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The paper contains an extension of results of \textit{D. S. Johnson, C. H. Papadimitriou} and \textit{M. Yannakakis} [``On generating all maximal independent sets'', Inf. Process. Lett. 27, 119--123 (1988; Zbl 0654.68086)].
    0 references
    algorithmics
    0 references
    biclique
    0 references
    enumeration
    0 references
    NP-completeness
    0 references
    lexicographic order
    0 references
    polynomial-time delay
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references