Succinct Encodings for Families of Interval Graphs
| Autor: | Sankardeep Chakraborty, Srinivasa Rao Satti, Hüseyin Acan, Seungbum Jo |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Algoritmer og beregnbarhetsteori: 422 [VDP]
General Computer Science Degree (graph theory) Applied Mathematics Interval graph Algorithms and computability theory: 422 [VDP] 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Combinatorics Succinct data structure Succinctness 010201 computation theory & mathematics Independent set Shortest path problem 0202 electrical engineering electronic engineering information engineering Adjacency list Interval (graph theory) 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Algorithmica |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-020-00710-w |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink