On bandwidth, cutwidth, and quotient graphs

DOI10.1051/ita/1995290604871zbMath0881.68089OpenAlexW1522005659MaRDI QIDQ4359287

François Pellegrini, Jean Roman, Dominique Barith, Andre Raspaud

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

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

Related Items (8)

New results on edge-bandwidth ⋮ On the queue number of planar graphs ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Bisecting de Bruijn and Kautz graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ Cutwidth of the de Bruijn graph ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Multiplicity of finite graphs over the real line

Cites Work

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

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