Arrow Research search

Author name cluster

Arash Farzan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

TCS Journal 2013 Journal Article

Succinct encoding of arbitrary graphs

  • Arash Farzan
  • J. Ian Munro

We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the Θ ( log n ) -bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m = o ( n δ ) for any constant δ > 0 ) or too dense (namely m = ω ( n 2 − δ ) for any constant δ > 0 ). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1 + ϵ factor of the information-theory lower bound for any arbitrarily small constant ϵ > 0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse ( m = o ( n δ ) for any constant δ > 0 ), or very dense ( m > n 2 / lg 1 − δ n for an arbitrarily small constant δ > 0 ).

Details DOI

TCS Journal 2011 Journal Article

Succinct representation of dynamic trees

  • Arash Farzan
  • J. Ian Munro

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree. We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively. We demonstrate that to efficiently support more extended operations, such as determining the i -th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time. Previous work on dynamic succinct trees (Munro et al. , 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al. , 2001 [17]) or “poly-log–log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log–log” query time (Gupta et al. , 2007 [11]). More recently, the update time has been improved to O ( log n / log log n ) while queries can be performed in O ( log n / log log n ) time (Sadakane and Navarro, 2010 [20]).

Details DOI
v2026.09.13