7 papers
Succinct Navigational Oracles for Families of Intersection Graphs on a Circle
Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo +3
We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood…
Perfect matchings and Hamilton cycles in uniform attachment graphs
Huseyin Acan
We study Hamilton cycles and perfect matchings in a uniform attachment graph. In this random graph, vertices are added sequentially, and when a vertex is created, it makes …
Giant descendant trees, matchings and independent sets in the age-biased attachment graphs
Huseyin Acan, Alan Frieze, Boris Pittel
We study two models of an age-biased graph process: the -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with attachme…
Succinct Data Structures for Families of Interval Graphs
Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo +1
We consider the problem of designing succinct data structures for interval graphs with vertices while supporting degree, adjacency, neighborhood and shortest path queries in op…
On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph
Hüseyin Acan, Boris Pittel
A uniform attachment graph (with parameter ), denoted in the paper, is a random graph on the vertex set , where each vertex makes selections from …
Counting unlabeled interval graphs
Hüseyin Acan
We improve the bounds on the number of interval graphs on vertices. In particular, denoting by the quantity in question, we show that as $n\to \in…