000			02234nam a22002057a 4500
999			_c52256 _d52256
008			180803s2018 ii ||||| |||| 00| 0 eng d
041			_aeng
080			_aHBNI _bTh134
100			_aSankar Deep Chakraborty _eauthor
245			_aSpace efficient graph algorithms
260			_c2018
300			_a235p.
502			_bPh.D _cHBNI _d2018
520			_aDue 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 algorithms for fundamental graph problems using little space without compromising on the speed as well. We provide such algorithms for various graph search methods (depth-first search, breadth-first search, maximum cardinality search) and fundamental connectivity prob- 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. We also provide sub-linear bits algorithms for various optimization problems on bounded treewidth graphs in the read-only memory model. In fact, we prove the following more 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. Furthermore, we introduce two new frameworks for designing efficient in-place graph algorithms (where the input elements can be moved around in a restricted way) and obtain such algorithms for several basic algorithmic graph problems. In particular, we develop algorithms for depth-first search and breadth-first search in these models 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			_aComputer Science
690			_aComputer Science
720			_aVenkatesh Raman _eThesis Advisor [ths]
856			_uhttps://www.imsc.res.in/xmlui/handle/123456789/420
942			_cTHESIS