Improved Bandwidth Approximation for Trees and Chordal Graphs

DOI10.1006/jagm.2000.1118zbMath0979.68066OpenAlexW1984672232MaRDI QIDQ2746436

Anupam Gupta

Publication date: 10 October 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2000.1118

zbMATH Keywords

\(n\)-vertex graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

On semidefinite programming bounds for graph bandwidth ⋮ Approximating the bandwidth of caterpillars ⋮ Graph bandwidth of weighted caterpillars ⋮ Hardness results for approximating the bandwidth ⋮ Volume in general metric spaces ⋮ Thread Graphs, Linear Rank-Width and Their Algorithmic Applications ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Combinatorial theorems about embedding trees on the real line ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ On the graph turnpike problem