Succinct navigational oracles for families of intersection graphs on a circle

Autor: Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Kei Nakashima, Kunihiko Sadakane, Srinivasa Rao Satti

Publikováno v: Theoretical Computer Science. 928:151-166

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood efficiently for intersection graphs on a circle, which include graph

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b202f8b2a87ca742e8c6a59bccc0972a
https://doi.org/10.1016/j.tcs.2022.06.022

Energy Efficient Sorting, Selection and Searching

Autor: Varunkumar Jayapaul, Seungbum Jo, Krishna Palem, Srinivasa Rao Satti

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783031270505

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::794521343eb321ddfe4ad7227c7ac52f
https://doi.org/10.1007/978-3-031-27051-2_16

Succinct Encodings for Families of Interval Graphs

Autor: Sankardeep Chakraborty, Srinivasa Rao Satti, Hüseyin Acan, Seungbum Jo

Publikováno v: Algorithmica

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 $$

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21a6bfa104415a6e7632b88f1a3b8885
https://doi.org/10.1007/s00453-020-00710-w

Succinct Representation for (Non)Deterministic Finite Automata

Autor: Roberto Grossi, Kunihiko Sadakane, Srinivasa Rao Satti, Sankardeep Chakraborty

Publikováno v: Language and Automata Theory and Applications-15th International Conference (LATA)
Language and Automata Theory and Applications-15th International Conference (LATA), 2021, Milan, Italy. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
LATA 2021-15th International Conference on Language and Automata Theory and Applications
LATA 2021-15th International Conference on Language and Automata Theory and Applications, Sep 2021, Milan, Italy. pp.55-67, ⟨10.1007/978-3-030-68195-1_5⟩
Journal of Computer and System Sciences
Journal of Computer and System Sciences, 2023, 131, pp.1-12. ⟨10.1016/j.jcss.2022.07.002⟩
Journal of computer & systems sciences international
Language and Automata Theory and Applications ISBN: 9783030681944
LATA

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::05581c1711ea8f56c2af1351ae4aa321
https://doi.org/10.2139/ssrn.4069236

Succinct representations of Intersection Graphs on a Circle

Autor: Hüseyin Acan, Sankardeep Chakraborty, Kei Nakashima, Seungbum Jo, Kunihiko Sadakane, Srinivasa Rao Satti

Publikováno v: DCC

We consider the problem of designing succinct encodings for some intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs among others. More specifically, we first prove a ge

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ac8053cd4f7a5597c38fe1adc816223a
https://doi.org/10.1109/dcc50243.2021.00020