Cutwidth of the de Bruijn graph

DOI10.1051/ITA/1995290605091MaRDI QIDQ4359288zbMATH OpenOpenAlexFDO

Authors Ondrej Sýkora, Imrich Vrt'o, André 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

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

Recommendations

• On bandwidth, cutwidth, and quotient graphs
• A better upper bound on the bisection width of de Bruijn networks (extended abstract)
• scientific article; zbMATH DE number 1854105
• Bisecting de Bruijn and Kautz graphs

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3900683 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Area-time lower-bound techniques with applications to sorting
• Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$
• On bandwidth, cutwidth, and quotient graphs
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Cited in

(9)

• Strong SDP based bounds on the cutwidth of a graph
• Graph parameters measuring neighbourhoods in graphs-bounds and applications
• Wide diameters of de Bruijn graphs
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Minimal cutwidth linear arrangements of abelian Cayley graphs
• A better upper bound on the bisection width of de Bruijn networks (extended abstract)
• Bounds on mincut for Cayley graphs over Abelian groups
• Cutwidth of the \(r\)-dimensional mesh of \(d\)-ary trees
• Branch and bound for the cutwidth minimization problem

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

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