Algorithms for maximum independent set in convex bipartite graphs

DOI10.1007/S00453-007-9006-9MaRDI QIDQ1017904zbMATH OpenOpenAlexFDO

Authors J. Martínez

Publication date 13 May 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9006-9

zbMATH Keywords

BSP/CGM algorithmsconvex bipartite graphsindependent setsparallel algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parallel maximum independent set in convex bipartite graphs
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Finding maximum edge bicliques in convex bipartite graphs
• scientific article; zbMATH DE number 1696524

Cites work

• A linear time algorithm for maximum matchings in convex, bipartite graphs
• scientific article; zbMATH DE number 1696524 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1256741 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Maximum matching in a convex bipartite graph
• Parallel maximum independent set in convex bipartite graphs
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(13)

• Parallel maximum independent set in convex bipartite graphs
• Finding maximum edge bicliques in convex bipartite graphs
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Advice complexity of maximum independent set in sparse and bipartite graphs
• scientific article; zbMATH DE number 1696524 (Why is no real title available?)
• Finding maximum edge bicliques in convex bipartite graphs
• Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
• Total domination and open packing in some subclasses of bipartite graphs
• Happy set problems on cubic graphs and convex bipartite graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Connected partitions via connected dominating sets
• An optimal maximal independent set algorithm for bounded-independence graphs

This page was built for publication: Algorithms for maximum independent set in convex bipartite graphs

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