Approximating Bandwidth by Mixing Layouts of Interval Graphs

DOI10.1137/S0895480199359624MaRDI QIDQ4785694zbMATH OpenFDO

Authors Dieter Kratsch, Lorna Stewart

Publication date 5 January 2003

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199359624

zbMATH Keywords

approximation algorithmbandwidth problemchordal graphscircular-arc graphsinterval graphspolygon graphs

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating bandwidth by mixing layouts of interval graphs
• scientific article; zbMATH DE number 1304325
• scientific article; zbMATH DE number 3974992
• Improved bandwidth approximation for trees and chordal graphs
• Hardness results for approximating the bandwidth

Cited in

(12)

• Cubicity and bandwidth
• On polygon numbers of circle graphs and distance hereditary graphs
• Approximating bandwidth by mixing layouts of interval graphs
• On the cubicity of AT-free graphs and circular-arc graphs
• Reduced clique graphs of chordal graphs
• scientific article; zbMATH DE number 1304325 (Why is no real title available?)
• Line-distortion, bandwidth and path-length of a graph
• Parameterized complexity of multicut in weighted trees
• Hardness results for approximating the bandwidth
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Domination and cut problems on chordal graphs with bounded leafage
• The interval-merging problem

This page was built for publication: Approximating Bandwidth by Mixing Layouts of Interval Graphs

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