An optimal PRAM algorithm for a spanning tree on trapezoid graphs.

DOI10.1007/BF02936178zbMath1103.68979MaRDI QIDQ1432796

Debashis Bera, Madhumangal Pal, Tapan Kumar Pal

Publication date: 22 June 2004

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (1)

A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• A parallel algorithm for eliminating cycles in undirected graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs

This page was built for publication: An optimal PRAM algorithm for a spanning tree on trapezoid graphs.