Parallel maximum independent set in convex bipartite graphs

DOI10.1016/0020-0190(96)00131-7zbMath0875.68706OpenAlexW2019881664MaRDI QIDQ1350905

Krzysztof Diks, Artur Czumaj, Teresa M. Przytycka

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00131-7

zbMATH Keywords

Bipartite graphsIndependent setPRAM algorithmsConvex graphs

Mathematics Subject Classification ID

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

Related Items (2)

Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ Algorithms for maximum independent set in convex bipartite graphs

Cites Work

• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Testing for Equality between Maximum Matching and Minimum Node Covering
• Faster optimal parallel prefix sums and list ranking
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• A simple parallel tree contraction algorithm
• Maximum matching in a convex bipartite graph

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