Succinct data structure for path graphs ☆

Article Computer Science, Hardware & Architecture

Succinct representation for (non)deterministic finite automata

Sankardeep Chakraborty et al.

Summary: (Non)-Deterministic finite automata, one of the simplest models of computation in automata theory, are studied in this paper through the lens of succinct data structures. The authors propose a data structure for deterministic automaton D that can determine whether D accepts a given string x in optimal time. Various time-space trade-offs are also considered. The authors also present a data structure for non-deterministic automaton N and provide efficient algorithms for performing standard operations on languages accepted by finite automata.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2023)

添加到收藏夹

Article Computer Science, Theory & Methods

Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number

Sankardeep Chakraborty et al.

Summary: In this paper, we propose parameterized compact data structures for interval graphs with bounded degree or bounded chromatic number. The space requirements for our data structures are analyzed, and it is shown that they take less space than existing upper bound results. Additionally, we introduce a new data structure for interval graphs with bounded chromatic number, which is more efficient than previous approaches. Finally, we extend our study to circular-arc graphs and provide parameterized compact data structures under degree or chromatic number constraints.

THEORETICAL COMPUTER SCIENCE (2023)

添加到收藏夹

Article Computer Science, Theory & Methods

Succinct navigational oracles for families of intersection graphs on a circle

Huseyin Acan et al.

Summary: This paper investigates the problem of designing succinct navigational oracles and proposes a unified approach to represent various graph classes. The paper provides lower and upper bounds for these classes using a unified technique.

THEORETICAL COMPUTER SCIENCE (2022)

添加到收藏夹

Article Computer Science, Interdisciplinary Applications