Shodhganga : a reservoir of Indian theses @ INFLIBNET
The Shodhganga@INFLIBNET Centre provides a platform for research students to deposit their Ph.D. theses and make it available to the entire scholarly community in open access.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10603/456491
| Title: | Algorithms for some steiner tree problems on graphs |
| Researcher: | Saikia, Parikshit |
| Guide(s): | Karmakar, Sushanta |
| Keywords: | Computer Science Computer Science Theory and Methods Engineering and Technology |
| University: | Indian Institute of Technology Guwahati |
| Completed Date: | 2020 |
| Abstract: | In this research work we study the Steiner tree ST problem in the distributed setting Given a connected undirected graph with non negative edge weights and a subset of terminal nodes the goal of the ST problem is to find a minimum cost tree spanning the terminals The first contribution is a deterministic distributed algorithm for the ST problem DST algorithm in the CONGEST model which guarantees an approximation factor of 2 1 226 710 8217 1 226 8222 8220 where 226 8222 8220 is the number of leaf nodes in the optima... |
| Pagination: | Not Available |
| URI: | http://hdl.handle.net/10603/456491 |
| Appears in Departments: | Department of Computer Science and Engineering |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 01_fulltext.pdf | Attached File | 3.08 MB | Adobe PDF | View/Open |
| 04_abstract.pdf | 454.56 kB | Adobe PDF | View/Open | |
| 80_recommendation.pdf | 299.75 kB | Adobe PDF | View/Open |
Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).
Altmetric Badge: