Cutwidth of the de Bruijn graph

DOI10.1051/ita/1995290605091zbMath0880.05054OpenAlexW102750817MaRDI QIDQ4359288

Imrich Vrt'o, Ondrej Sýkora, Andre Raspaud

Publication date: 8 October 1997

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92521

zbMATH Keywords

upper boundde Bruijn graphcutwidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (7)

Branch and bound for the cutwidth minimization problem ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ Cutwidth of ther-dimensional Mesh ofd-ary Trees ⋮ Minimal cutwidth linear arrangements of abelian Cayley graphs ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Bounds on mincut for Cayley graphs over Abelian groups

Cites Work

• Unnamed Item
• Unnamed Item
• Area-time lower-bound techniques with applications to sorting
• A polynomial algorithm for the min-cut linear arrangement of trees
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$
• On bandwidth, cutwidth, and quotient graphs

This page was built for publication: Cutwidth of the de Bruijn graph