Approximating Bandwidth by Mixing Layouts of Interval Graphs
From MaRDI portal
Publication:4785694
DOI10.1137/S0895480199359624zbMath1006.05052MaRDI QIDQ4785694
Dieter Kratsch, Lorna K. Stewart
Publication date: 5 January 2003
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
approximation algorithmchordal graphsinterval graphscircular-arc graphsbandwidth problempolygon graphs
Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (8)
The interval-merging problem ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Parameterized complexity of multicut in weighted trees ⋮ Hardness results for approximating the bandwidth ⋮ Cubicity and bandwidth ⋮ Reduced clique graphs of chordal graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs
This page was built for publication: Approximating Bandwidth by Mixing Layouts of Interval Graphs
