Algorithms for induced biclique optimization problems

DOI10.1016/J.IPL.2011.02.005MaRDI QIDQ1944925zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 28 March 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.02.005

zbMATH Keywords

graph algorithmspolygon-circle graphproteininterval-filament graphinduced balanced bicliqueinduced bicliqueprotein-interaction

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Efficient enumeration of maximal induced bicliques
• Exact exponential-time algorithms for finding bicliques
• On problem of finding all maximal induced bicliques of hypergraph
• Maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs and circle graphs
• Near optimal solutions for maximum quasi-bicliques

Cites work

• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 3D-interval-filament graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms on Subtree Filament Graphs
• Bisimplicial vertices in even-hole-free graphs
• Complexity results on graphs with few cliques
• Covering and coloring polygon-circle graphs
• Efficient graph representations
• Formal Concept Analysis
• Induced matchings in intersection graphs.
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Node-Deletion Problems on Bipartite Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Subtree filament graphs are subtree overlap graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The maximum edge biclique problem is NP-complete
• Triangulated neighborhoods in even-hole-free graphs

Cited in

(8)

• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• On problem of finding all maximal induced bicliques of hypergraph
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Mixed Integer Programming for Searching Maximum Quasi-Bicliques
• Maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs and circle graphs
• Parameterized algorithms for edge biclique and related problems
• Algorithms for maximum weight induced paths
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

This page was built for publication: Algorithms for induced biclique optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944925)