School of Technology and Computer Science Seminars

Coloring, Embedding, Compression and Data Structure Problems on Uniform Hypergraphs

by Mr. Saswata Shannigrahi (School of Technology and Computer Science)

Tuesday, January 11, 2011 from to (Asia/Kolkata)
at Colaba Campus ( AG-69 )
Description
We study four problems on uniform hypergraph. First, we present a streaming algorithm for two-coloring uniform hypergraphs with limited number of hyperedges. Second, we show relationships between four different geometric parameters of the embedding of a complete 3-uniform hypergraph in 3-dimensional space. Third, we present a compression scheme for uniform hypertrees, which are generalizations of trees. Finally, we present a data structure for succinctly storing a hyperedge of a complete uniform hypergraph in order to support membership queries in the bitprobe model.
Organised by John Barretto