IJPAM: Volume 109, No. 7 (2016)

Title

CUTWIDTH OF CERTAIN CLASSES
OF CIRCULANT NETWORKS

Authors

A. Berin Greeni$^1$, Indra Rajasingh$^2$
$^{1,2}$School of Advanced Sciences
VIT University
Chennai, INDIA

Abstract

The cutwidth problem of a graph $G$ is to embed $G$ into a path such that the maximum number of edges crossing along any cut in the path is minimized. A circulant graph $C_{mk} (1, k)$ is a graph with vertex set $V = {\{1,2,\ldots,mk\}}$ and edge set $ E = E_{1}\cup E_{2}$, where

\begin{displaymath}E_1 = \{(i, i+1)\},\quad E_2 = \{(i, (i+k)~mod \ mk)\}, \quad i \in \{1, 2, 3,\ldots, mk\}.\end{displaymath}

Bansal et al. (IEEE World Congress on Computational Intelligence, 2012) conjectured that the cutwidth of $ C_{2k} (1, k), 3< k \leq 30 $ is 5. In this paper we not only prove this conjecture but also prove that the result is true for any $k, k>3$.

History

Received: October 1, 2016
Revised:
Published: February 20, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C78
Key Words and Phrases: circulant graphs, cutwidth, minimum cut, layout, minimum cut arrangement problem, graph layout

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
F. Gavril, Some NP-complete problems on graphs, 11th Conference on Information Sciences and Systems, Baltimore, 91 - 95, 1977.

2
B. Monien, I.H. Sudborough, Min cut is NP-complete for edge weighted trees, Theoretical Computer Science, Vol. 58, no. 1-3, 209 - 229, 1988.

3
J. Diaz, M.D. Penrose, J.Petit, M.J. Serna, Layout problems on lattice graphs, Computing and Combinatorics, Lecture Notes in Computer Science, Vol. 1627, 103 - 112, 1999.

4
D.M. Thilikos, M.J. Serna, H.L. Bodlaender, Cutwidth II: Algorithms for partial w-trees of bounded degree, Journal of Algorithms, Vol. 56, 24 - 49, 2005.

5
D. Adolphson, T.C. Hu, Optimal linear ordering, SIAM J. Appl. Math., Vol. 25, 403 - 423, 1973.

6
F. Makedon, I.H. Sudborough, On minimizing width in linear layouts, Discrete Applied Mathematics, Vol. 23, p. 243 - 265, 1989.

7
G. Blin, G. Fertin, D. Hermelin, S. Vialette, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Journal of Discrete Algorithms, Vol. 6, 618 - 626, 2008.

8
D.R. Karger, A randomized fully polynomial approximation scheme for the all-terminal network reliability problem, SIAM Journal on Computing, Vol. 29, 492 - 514, 1999.

9
P. Mutzel, A polyhedral approach to planar augmentation and related problems, Proceedings of ESA 1995, LNCS 979, 497 - 507, 1995.

10
R.A. Botafogo, Cluster analysis for hypertext systems, Proceedings of SIGIR, ACM, 116 - 125, 1993.

11
J. Petit, Addenda to the survey of layout problems, Bulletin of the EATCS, no.105, 177 - 201, 2011.

12
J. Rolim, O. Sykora, I. Vrto, Optimal cutwidths and bisection widths of $2$- and $3$- dimensional meshes, Lecture Notes in Computer Science, Vol. 1017, 252 - 264, 1995.

13
L. Yixun, L. Xianglu, Y. Aifeng, A degree sequence method for the cutwidth problem of graphs, Appl. Math. J. Chinese Univ. Ser B, Vol. 17, no.2, 125 - 134, 2002.

14
P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos, Cutwidth of split graphs, threshold graphs, and proper interval graphs, Lecture Notes in Computer Science, Vol. 5344, 218 - 229, 2008.

15
E.T. Boesch and J.Wang, Reliable circulant networks with minimum transmission delay, IEEE Transactions on Circuit and Systems, Vol. 32, no. 12, 1286 - 1291, 1985.

16
G.K. Wong and D.A. Coppersmith, A combinatorial problem related to multimodule memory organization, Journal of Association for Computing Machinery, Vol. 21, no. 3, 392 - 401, 1994.

17
P. Manuel, M. Arockiaraj, I. Rajasingh and B. Rajan, Embeddings of circulant networks, Journal of Combinatorial Optimization, 2011.

18
J. Diaz, J.Petit, M.J. Serna, A survey of graph layout problems, ACM Computing Surveys, Vol. 34, 313 - 356, 2002.

19
J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, 2001.

20
I. Rajasingh, B. Rajan, R.S. Rajan, Embedding of special classes of circulant networks, hypercubes and generalized Peterson graphs, International Journal of Computer Mathematics, Vol. 89, no. 15, 1970 - 1978, 2010.

21
R. Bansal, R. Srivastava, K. Srivastava, Hybrid evolutionary algorithm for the cutwidth minimization problem, WCCI 2012, IEEE World Congress on Computational Intelligence, Brisbane, 10 - 15, 2012.

22
P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercube on a grid, Discrete Applied Mathematics, Vol. 157, no. 7, 1486 - 1495, 2009.

How to Cite?

DOI: 10.12732/ijpam.v109i7.13 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 109
Issue: 7
Pages: 101 - 108


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).