Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic traceability, and in this paper, we study the class of bounded clique-width graphs through the lens of succinct data structures. A data structure is said ...

We consider the problem of designing a succinct data structure for path graphs, that generalizes interval graphs, on n vertices while efficiently supporting degree, adjacency, and neighbourhood queries. We provide the following two solutions for ...

(Non)-Deterministic finite automata are one of the simplest models of computation studied in automata theory. Here we study them through the lens of succinct data structures. Towards this goal, we design a data structure for any ...

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

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-...$$$$

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient ...

In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who knows the entire road network in advance, and wishes to travel as quickly as ...$\mathrm{}\mathrm{}$$\mathrm{}$$\mathrm{}\mathrm{}$$\mathrm{}\frac{\sqrt{\mathrm{}}}{\mathrm{}}\sqrt{\mathrm{}}$

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study ...$\mathcal{}$$$$$$\mathrm{}\mathrm{}\mathrm{}$$$$\mathcal{}$$$$\mathcal{}$$\mathrm{}\mathrm{}{}^{\mathrm{}}$$$$\mathcal{}$$\mathcal{}$$$$$${}^{\mathrm{}}$$\mathcal{}$${}^{\mathrm{}}$

We present linear time in-place algorithms for several fundamental graph problems including the well-known graph search methods (like depth-first search, breadth-first search, maximum cardinality search), connectivity problems (like biconnectivity,...

We study node similarity in labeled networks, using the label sequences found in paths of bounded length q leading to the nodes. (This recalls the q-grams employed in document resemblance, based on the Jaccard distance.) When applied to networks, the ...

Let be a text of length n and be the suffix starting at position i. Also, for any two strings X and Y, let denote their longest common prefix. The range-LCP of w.r.t. a range , where is

We show that both the Lempel---Ziv-77 and the Lempel---Ziv-78 factorization of a text of length n on an integer alphabet of size $$\sigma $$ź can be computed in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}\left( n\right) $$On time with either $$\...

ZDDs Zero-suppressed Binary Decision Diagrams [Minato 93] have been proposed to store set families compactly. Though more compact than other representations, they still use large amount of memory to support dynamic operations such as taking union and ...

In memory-constrained algorithms, access to the input is restricted to be read-only, and the number of extra variables that the algorithm can use is bounded. In this paper we introduce the compressed stack technique, a method that allows to transform ...

In genome assembly graphs, motifs such as tips, bubbles, and cross links are studied in order to find sequencing errors and to understand the nature of the genome. Superbubble, a complex generalization of bubbles, was recently proposed as an important ...

The de Bruijn graph GK of a set of strings Sis a key data structure in genome assembly that represents overlaps between all the K-length substrings of S. Construction and navigation of the graph is a space and time bottleneck in practice and the main ...

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 ^w nodes under the unit-cost RAM model with a fixed word ...

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, ...

In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a ...