On bandwidth, cutwidth, and quotient graphs

DOI10.1051/ITA/1995290604871MaRDI QIDQ4359287zbMATH OpenOpenAlexFDO

Authors François Pellegrini, D. Barth, André Raspaud, J. Roman

Publication date 16 November 1997

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

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

zbMATH Keywords

bandwidthcutwidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Network design and communication in computer systems (68M10)

Recommendations

• Cutwidth of the de Bruijn graph
• Bounding the bandwidths for graphs
• scientific article; zbMATH DE number 1854105
• Bisection width of transposition graphs

Cites work

• scientific article; zbMATH DE number 4147467 (Why is no real title available?)
• scientific article; zbMATH DE number 3733986 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A Comparison of Several Bandwidth and Profile Reduction Algorithms
• Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• Placement of the processors of a hypercube
• The NP-completeness of the bandwidth minimization problem
• The bandwidth problem for graphs and matrices—a survey

Cited in

(13)

• Bisecting de Bruijn and Kautz graphs
• On the queue number of planar graphs
• A better upper bound on the bisection width of de Bruijn networks (extended abstract)
• Cutwidth of the de Bruijn graph
• An improved upper bound on the queue number of planar graphs
• Multiplicity of finite graphs over the real line
• New results on edge-bandwidth
• Graphs with small bandwidth and cutwidth
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Compact representation of graphs with bounded bandwidth or treedepth
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
• Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes
• scientific article; zbMATH DE number 1854105 (Why is no real title available?)

This page was built for publication: On bandwidth, cutwidth, and quotient graphs

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