Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Journal article
Succinct Encodings for Families of Interval Graphs
Algorithmica, v 83(3), pp 776-794
01 Mar 2021
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 Am Math Soc Ser B 4(1):1-3, 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 interval graphs, 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.
Metrics
Details
- Title
- Succinct Encodings for Families of Interval Graphs
- Creators
- Huseyin Acan - Drexel UniversitySankardeep Chakraborty - National Institute of InformaticsSeungbum Jo - Chungbuk National UniversitySrinivasa Rao Satti - SEOUL NATIONAL UNIVERSITY Seoul, South Korea
- Publication Details
- Algorithmica, v 83(3), pp 776-794
- Publisher
- Springer Nature
- Number of pages
- 19
- Grant note
- 1502650 / National Science Foundation Fellowship; National Science Foundation (NSF) MISU F 6001 1 / Fonds de la Recherche Scientifique-FNRS; Fonds de la Recherche Scientifique - FNRS 18H05291 / JSPS KAKENHI; Ministry of Education, Culture, Sports, Science and Technology, Japan (MEXT); Japan Society for the Promotion of Science; Grants-in-Aid for Scientific Research (KAKENHI) Chungbuk National University
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000528520900002
- Scopus ID
- 2-s2.0-85084128471
- Other Identifier
- 991019167921604721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Software Engineering
- Mathematics, Applied