Space efficient graph algorithms (Record no. 52256)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02234nam a22002057a 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 180803s2018 ii ||||| |||| 00| 0 eng d |
| 041 ## - LANGUAGE CODE | |
| Language code of text/sound track or separate title | eng |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI |
| Item number | Th134 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Sankar Deep Chakraborty |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Space efficient graph algorithms |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2018 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 235p. |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| Name of granting institution | HBNI |
| Year degree granted | 2018 |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | Due to the rapid growth of data, algorithms that utilize the space efficiently are increasingly becoming important. This thesis focusses on an emerging area of designing<br/> algorithms for fundamental graph problems using little space without compromising<br/> on the speed as well.<br/> We provide such algorithms for various graph search methods (depth-first search,<br/> breadth-first search, maximum cardinality search) and fundamental connectivity prob-<br/> lems (biconnectivity, 2-edge connectivity and strong connectivity) in the read-only memory model using O(n) bits of extra space. Most of these results require techniques from succinct data structures along with suitable modifications of the existing graph algorithms.<br/> We also provide sub-linear bits algorithms for various optimization problems on bounded<br/> treewidth graphs in the read-only memory model. In fact, we prove the following more<br/> general meta theorem which says, for bounded treewidth graphs, if any graph problem can be described in monadic second order (MSO) logic, we can obtain a smooth deterministic time-space trade-off from logarithmic words to linear space.<br/> Furthermore, we introduce two new frameworks for designing efficient in-place graph<br/> algorithms (where the input elements can be moved around in a restricted way) and<br/> obtain such algorithms for several basic algorithmic graph problems. In particular,<br/> we develop algorithms for depth-first search and breadth-first search in these models<br/> taking only O (log n) extra bits albeit taking super-linear time. In sharp contrast, we do not know of any algorithms for these problems taking sub-linear bits of space in the read-only memory model |
| 650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 690 ## - LOCAL SUBJECT ADDED ENTRY--TOPICAL TERM (OCLC, RLIN) | |
| Topical term or geographic name as entry element | Computer Science |
| 720 ## - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Venkatesh Raman |
| Relator term | Thesis Advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | https://www.imsc.res.in/xmlui/handle/123456789/420 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Collection code | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|---|
| IMSc Thesis | IMSc Library | HBNI Th134 | 74223 | https://www.imsc.res.in/xmlui/handle/123456789/420 | THESIS & DISSERTATION |