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

DOI10.1007/BF02936178MaRDI QIDQ1432796zbMATH OpenFDO

Authors Debashis Bera, Madhumangal Pal, Tapan K. 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

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

Recommendations

• A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph
• scientific article; zbMATH DE number 1117869
• scientific article; zbMATH DE number 1281573
• scientific article; zbMATH DE number 1960881
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 42739 (Why is no real title available?)
• A parallel algorithm for eliminating cycles in undirected graphs
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited in

(4)

• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• scientific article; zbMATH DE number 2092300 (Why is no real title available?)
• A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph

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

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