Discrete isoperimetric method for bandwidth, pathwidth and treewidth of hypercubes

DOI10.1016/J.DAM.2024.12.001MaRDI QIDQ6671397zbMATH OpenFDO

Authors Lan Lin, Yanpei Liu

Publication date 27 January 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.12.001

zbMATH Keywords

bandwidthgraph numberinghypercubespathwidthtreewidth

Mathematics Subject Classification ID

Distance in graphs (05C12) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The treewidth and pathwidth of hypercubes
• Isoperimetric inequalities and the width parameters of graphs
• The carvingwidth of hypercubes
• On explicit formulas for bandwidth and antibandwidth of hypercubes
• A spectral lower bound for the treewidth of a graph and its consequences

Cites work

• A note on Hamming spheres
• A partial k-arboretum of graphs with bounded treewidth
• A short proof for a theorem of Harper about Hamming-spheres
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph extensions and some optimization problems in sparse matrix computations
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph theory
• scientific article; zbMATH DE number 3852305 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 3570458 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• Nonserial dynamic programming
• Odd and even Hamming spheres also have minimum boundary
• On explicit formulas for bandwidth and antibandwidth of hypercubes
• Optimal numberings and isoperimetric problems on graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• The treewidth and pathwidth of hypercubes
• Two improved algorithms for envelope and wavefront reduction
• Weak-quasi-bandwidth and forward-bandwidth of graphs

This page was built for publication: Discrete isoperimetric method for bandwidth, pathwidth and treewidth of hypercubes

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