Algorithms for maximum independent set in convex bipartite graphs

DOI10.1007/s00453-007-9006-9zbMath1171.68648OpenAlexW2101075550MaRDI QIDQ1017904

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

parallel algorithmindependent setsconvex bipartite graphsBSP/CGM algorithms

Mathematics Subject Classification ID

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

Related Items (4)

Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parallel maximum independent set in convex bipartite graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Maximum matching in a convex bipartite graph
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS

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