On the cubicity of bipartite graphs
Data(s) |
01/04/2009
|
---|---|
Resumo |
A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k, where each R-i is a closed interval on the real line of the form [a(j), a(i), + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for graph G, cub(G) <= left perpendicular2n/3right perpendicular. Recently it has been shown that for a graph G, cub(G) >= 4(Delta + 1) In n, where n and Delta are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A boolean OR B, E) with |A| = n(1), |B| = n2, n(1) <= n(2), and Delta' = min {Delta(A),Delta(B)}, where Delta(A) = max(a is an element of A)d(a) and Delta(B) = max(b is an element of B) d(b), d(a) and d(b) being the degree of a and b in G, respectively , cub(G) <= 2(Delta' + 2) bar left rightln n(2)bar left arrow. We also give an efficient randomized algorithm to construct the cube representation of G in 3 (Delta' + 2) bar right arrowIn n(2)bar left arrow dimension. The reader may note that in general Delta' can be much smaller than Delta. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/19890/1/pdf.pdf Chandran, L Sunil and Das, Anita and Sivadasan, Naveen (2009) On the cubicity of bipartite graphs. In: Information Processing Letters, 109 (9). pp. 432-435. |
Publicador |
Elsevier Science |
Relação |
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-4V8GB7M-5&_user=512776&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000025298&_version=1&_urlVersion=0&_userid=512776&md5=eda9826e22c172e4ee69e423d6ee3810 http://eprints.iisc.ernet.in/19890/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |