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

DOI10.1080/0020716031000112330MaRDI QIDQ4454318zbMATH OpenOpenAlexFDO

Authors Sukumar Mondal, Madhumangal Pal, Tapan K. 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

Steiner treeParallel algorithmsAnalysis of algorithmsPermutation graphsSteiner set

Mathematics Subject Classification ID

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

Recommendations

• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• Efficient parallel algorithms for permutation graphs
• Permutation graphs: Connected domination and Steiner trees
• Some Efficient Algorithms for Permutation Graphs
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
• Connected domination and Steiner set on weighted permutation graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Efficient parallel algorithms for permutation graphs
• Incremental modular decomposition
• Permutation graphs: Connected domination and Steiner trees
• Steiner trees, connected domination and strongly chordal graphs
• Topics on domination
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(4)

• Parallel local search for Steiner trees in graphs
• scientific article; zbMATH DE number 1796994 (Why is no real title available?)
• \(L(0,1)\)-labelling of permutation graphs
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

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

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