Record Details

The common prefix problem on trees

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title The common prefix problem on trees
 
Creator KENKRE, S
VISHWANATHAN, S
 
Subject approximation algorithms
common prefix
database query optimization
maximum edge biclique
 
Description We consider a problem arising in database query optimization [R. Guravannavar, S. Sudarshan, Reducing order enforcement cost in complex query plans, in: Proceedings of the 23rd IEEE International Conference on Data Engineering, ICDE-2007, pp. 856-865; R. Guravannavar, S. Sudarshan, A.A. Diwan, Ch. Sobhan Babu, Reducing order enforcement cost in complex query plans, Manuscript, November 2006. Available at http://arxiv.org/abs/cs.DB/0611094], which we call as The Common Prefix Problem. We present a PTAS for this problem, when the underlying graph is a tree with the degrees of the vertices bounded by a constant, e.g. binary tree. We then use a result of Feige and Kogan [U. Feige, S. Kogan, Hardness of approximation of the balanced complete bipartite subgraph problem, Technical report MCS04-04, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, 2004] to show that even on star graphs the problem is hard to approximate. (C) 2007
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-27T01:03:35Z
2011-12-26T12:52:57Z
2011-12-27T05:39:58Z
2011-07-27T01:03:35Z
2011-12-26T12:52:57Z
2011-12-27T05:39:58Z
2008
 
Type Article
 
Identifier INFORMATION PROCESSING LETTERS, 105(6), 245-248
0020-0190
http://dx.doi.org/10.1016/j.ipl.2007.08.032
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7069
http://hdl.handle.net/10054/7069
 
Language en