Space efficient graph algorithms
Material type: TextLanguage: English Publication details: 2018Description: 235pSubject(s): Computer Science | Computer ScienceOnline resources: Click here to access online Dissertation note: Ph.D HBNI 2018 Summary: 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 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 modelCurrent library | Home library | Collection | Call number | Materials specified | URL | Status | Date due | Barcode |
---|---|---|---|---|---|---|---|---|
IMSc Library | IMSc Library | IMSc Thesis | HBNI Th134 (Browse shelf (Opens below)) | Link to resource | Available | 74223 |
Browsing IMSc Library shelves Close shelf browser (Hides shelf browser)
Ph.D HBNI 2018
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
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
There are no comments on this title.