๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Bisection width of transposition graphs

โœ Scribed by Ladislav Stacho; Imrich Vrt'o

Book ID
104294923
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
894 KB
Volume
84
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

We prove lower and upper bounds on bisection width of transposition graphs. This class of graphs contains several frequently studied interconnection networks including star graphs and hypercubes. In particular, we prove that the bisection width of the complete transposition graph is of order O(n.n!) which solves the open problem (R) 3.356 of Leighton's book [IO] and determine an asymptotically exact value of bisection width of the star graph. The results have applications to VLSI layouts, cutwidth and crossing numbers of transposition graphs. We also study bandwidth of these graphs.

๐Ÿ“œ SIMILAR VOLUMES

The bisection width of grid graphs
The bisection width of grid graphs
โœ C. H. Papadimitriou, M. Sideri ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Springer ๐ŸŒ English โš– 752 KB
On the bisection width of the transposit
On the bisection width of the transposition network
โœ Kalpakis, Konstantinos; Yesha, Yaacov ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 103 KB ๐Ÿ‘ 3 views

The transposition network T n of order n! is the Cayley graph of the symmetric group S n with generators the set of all transpositions in S n . Finding the bisection width of the transposition network is an open question posed by F. T. Leighton. We resolve this question for n even, by showing that t

Bisections of graphs
Bisections of graphs
โœ Lee, Choongbum; Loh, Po-Shen; Sudakov, Benny ๐Ÿ“‚ Article ๐Ÿ“… 2013 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 458 KB
On judicious bisections of graphs
On judicious bisections of graphs
โœ Xu, Baogang; Yu, Xingxing ๐Ÿ“‚ Article ๐Ÿ“… 2014 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 536 KB