Finding maximum edge bicliques in convex bipartite graphs

DOI10.1007/s00453-010-9486-xzbMath1257.05170OpenAlexW2008088179WikidataQ62037433 ScholiaQ62037433MaRDI QIDQ1759663

Doron Nussbaum, Takeaki Uno, Shuye Pu, Jörg-Rüdiger Sack, Hamid Zarrabi-Zadeh

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.874.6788

zbMATH Keywords

bipartite permutation graphconvex bipartite graphbicliquebiconvex graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

The Bipartite QUBO ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ Unnamed Item ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Generating bicliques of a graph in lexicographic order
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Finding the largest area axis-parallel rectangle in a polygon
• Consensus algorithms for the generation of all maximal bicliques
• Algorithms for maximum independent set in convex bipartite graphs
• Enumeration aspects of maximal cliques and bicliques
• Geometric applications of a matrix-searching algorithm
• A log log n data structure for three-sided range queries
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• The maximum edge biclique problem is NP-complete
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• On Bipartite and Multipartite Clique Problems
• Inapproximability of Maximum Weighted Edge Biclique and Its Applications
• Dynamic Matchings in Convex Bipartite Graphs
• Relations between average case complexity and approximation complexity
• Graph Classes: A Survey
• Learning Theory and Kernel Machines
• Maximum matching in a convex bipartite graph
• Algorithms and Computation
• On the generation of bicliques of a graph

This page was built for publication: Finding maximum edge bicliques in convex bipartite graphs