2-WAY PARTITIONING OF SHUFFLE-EXCHANGE AND DEBRUIJN GRAPHS

Authors
KUCHLOUS A RAVIKUMAR CP
Citation
A. Kuchlous et Cp. Ravikumar, 2-WAY PARTITIONING OF SHUFFLE-EXCHANGE AND DEBRUIJN GRAPHS, Computer systems science and engineering, 10(2), 1995, pp. 84-91
Citations number
6
Categorie Soggetti
System Science","Computer Application, Chemistry & Engineering","Computer Sciences, Special Topics","Computer Science Theory & Methods
Journal title
Computer systems science and engineering → ACNP
ISSN journal
02676192
Volume
10
Issue
2
Year of publication
1995
Pages
84 - 91
Database
ISI
SICI code
0267-6192(1995)10:2<84:2POSAD>2.0.ZU;2-W
Abstract
In this paper we describe approximation algorithms for the two-way par tition of undirected shuffle-exchange and DeBruijn graphs. For n-bit S huffle-Exchange graphs, we provide an algorithm which gives a cut size of GRAPHICS if n is odd. If n is even, our algorithm gives a cut si ze no larger than GRAPHICS The same algorithm may also be used to ge nerate good partitions of DeBruijn graphs; we show that the bounds on the cutset size are doubled when the algorithm is applied to DeBruijn graphs.