An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs

DOI10.1016/0020-0190(95)00125-VzbMath0875.68694OpenAlexW2009278168MaRDI QIDQ671937

Chen-Yu Lee, Yue-Li Wang, Hon-Chan Chen

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(95)00125-v

zbMATH Keywords

Parallel algorithmsGraph theorySpanning treePermutation graphsEREW computational model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (3)

An optimal PRAM algorithm for a spanning tree on trapezoid graphs. ⋮ On graphs associated to sets of rankings ⋮ Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• 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
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs

This page was built for publication: An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs