Efficient parallel algorithms for doubly convex-bipartite graphs

DOI10.1016/0304-3975(94)00220-DMaRDI QIDQ672468zbMATH OpenOpenAlexFDO

Authors Gen-Huey Chen, C. W. Yu

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)00220-d

zbMATH Keywords

bipartite graphCREW PRAM

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1696524
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Efficient parallel algorithms for bipartite permutation graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• scientific article; zbMATH DE number 3972201
• Efficient parallel algorithms for graph problems
• scientific article; zbMATH DE number 4068310
• Efficient parallel graph algorithms for coarse-grained multicomputers and BSP
• Efficient parallel graph algorithms for coarse grained multicomputers and BSP
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

Cites work

• An efficient parallel algorithm for planarity
• An O(logn) parallel connectivity algorithm
• Bipartite permutation graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient parallel algorithms for bipartite permutation graphs
• Efficient parallel algorithms for some graph problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximum matching in a convex bipartite graph
• NP-completeness of edge-colouring some restricted graphs
• On efficient parallel strong orientation
• Parallel Merge Sort
• Parallel recognition of the consecutive ones property with applications

Cited in

(18)

• Algorithms for maximum independent set in convex bipartite graphs
• Parallel maximum independent set in convex bipartite graphs
• Biconvex graphs: Ordering and algorithms
• Finding maximum edge bicliques in convex bipartite graphs
• Optimal computation of shortest paths on doubly convex bipartite graphs
• On strict (outer-)confluent graphs
• Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph
• scientific article; zbMATH DE number 1696524 (Why is no real title available?)
• An Efficient Parallel Biconnectivity Algorithm
• Doubling Algorithms with Permuted Lagrangian Graph Bases
• On strict (outer-)confluent graphs
• On the complexity of the maximum biplanar subgraph problem
• Path eccentricity of graphs
• L(2,1)-labeling of perfect elimination bipartite graphs
• Decomposing convex bipartite graphs into biconvex graphs and enumerating minimum weight red blue dominating sets
• Boundedness for proper conflict-free and odd colorings
• Radio labeling of biconvex split graphs
• Domination and packing in graphs

This page was built for publication: Efficient parallel algorithms for doubly convex-bipartite graphs

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