Minimal cutwidth linear arrangements of abelian Cayley graphs

DOI10.1016/J.DISC.2007.08.083MaRDI QIDQ942098zbMATH OpenOpenAlexFDO

Authors Vladimir Lipets, Daniel Berend, Ephraim Korach

Publication date 4 September 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.08.083

zbMATH Keywords

Cayley graphcombinatorial optimizationgraph algorithmMINCUT linear arrangement

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Bounds on mincut for Cayley graphs over Abelian groups
• On minimizing width in linear layouts
• On minimum cuts and the linear arrangement problem
• On small cuts separating an abelian Cayley graph into two equal parts
• Refined connectivity properties of abelian Cayley graphs

Cites work

• A polyhedral approach to planar augmentation and related problems
• A polynomial algorithm for the min-cut linear arrangement of trees
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Complexity Results for Bandwidth Minimization
• Cutwidth of the de Bruijn graph
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 4147467 (Why is no real title available?)
• scientific article; zbMATH DE number 3946174 (Why is no real title available?)
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• scientific article; zbMATH DE number 176780 (Why is no real title available?)
• scientific article; zbMATH DE number 3630808 (Why is no real title available?)
• Incidence matrices, interval graphs and seriation in archeology
• Mapping the genome
• On minimizing width in linear layouts
• Optimal Linear Ordering
• Parallel iterative methods for sparse linear systems
• Single Machine Job Sequencing with Precedence Constraints
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Cited in

(2)

• A note on minimum linear arrangement for BC graphs
• Bounds on mincut for Cayley graphs over Abelian groups

This page was built for publication: Minimal cutwidth linear arrangements of abelian Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q942098)