The Common Prefix Problem On Trees

Simple item page
dc.creatorKenkre, Sreyash
dc.creatorVishwanathan, Sundar
dc.date2006-12-11
dc.date.accessioned2026-07-07T07:31:52Z
dc.date.available2026-07-07T07:31:52Z
dc.descriptionWe present a theoretical study of a problem arising in database query optimization, which we call as The Common Prefix Problem. We present a $(1-o(1))$ factor approximation algorithm for this problem, when the underlying graph is a binary tree. We then use a result of Feige and Kogan to show that even on stars, the problem is hard to approximate.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/cs/0612060
dc.identifierhttp://arxiv.org/abs/cs/0612060
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/118912
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleThe Common Prefix Problem On Trees
dc.typetext

Files

Collections

arXiv