Minimal cutwidth linear arrangements of abelian Cayley graphs

We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each order.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-10, Vol.308 (20), p.4670-4695
Main Authors: Berend, Daniel, Korach, Ephraim, Lipets, Vladimir
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Cayley graph
Combinatorial optimization
Computer science
control theory
systems
Exact sciences and technology
Graph algorithm
MINCUT linear arrangement
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each order.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.08.083