Publications
Detailed Information
Succinct Data Structures for Families of Interval Graphs
Cited 9 time in
Web of Science
Cited 5 time in Scopus
- Authors
- Issue Date
- 2019-08
- Publisher
- Springer Verlag
- Citation
- Lecture Notes in Computer Science, Vol.11646, pp.1-13
- Abstract
- We consider the problem of designing succinct data structures for interval graphs with n vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time. Towards showing succinctness, we first show that at least n log(2) n-2n log(2) log(2) n-O(n) bits. are necessary to represent any unlabeled interval graph G with n vertices, answering an open problem of Yang and Pippenger [Proc. Amer. Math. Soc. 2017]. This is augmented by a data structure of size n log(2) n + O(n) bits while supporting not only the above queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on interval graphs efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit, k-improper interval graphs, and circular-arc graphs, and design succinct data structures for these graph classes as well along with supporting queries on them efficiently.
- ISSN
- 0302-9743
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.