Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

DOI10.1080/0020716031000112330zbMath1066.68158OpenAlexW2028478987MaRDI QIDQ4454318

Sukumar Mondal, Madhumangal Pal, Tapan Kumar Pal

Publication date: 8 March 2004

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/0020716031000112330

zbMATH Keywords

Parallel algorithmsSteiner treeSteiner setAnalysis of algorithmsPermutation graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

\(L(0,1)\)-labelling of permutation graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• Permutation graphs: Connected domination and Steiner trees
• Topics on domination
• Connected domination and Steiner set on weighted permutation graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Efficient parallel algorithms for permutation graphs
• Steiner trees, connected domination and strongly chordal graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Incremental modular decomposition
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs