On bandwidth, cutwidth, and quotient graphs

DOI10.1051/ITA/1995290604871zbMATH Open0881.68089OpenAlexW1522005659MaRDI QIDQ4359287FDOQ4359287

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• The NP-completeness of the bandwidth minimization problem
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Title not available (Why is that?)
• The bandwidth problem for graphs and matrices—a survey
• Title not available (Why is that?)
• 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)$
• Title not available (Why is that?)
• Placement of the processors of a hypercube

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
• Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes
• Title not available (Why is that?)
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning

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)