Approximating bandwidth by mixing layouts of interval graphs

MaRDI QIDQ2741348zbMATH OpenFDO

Authors Dieter Kratsch, Lorna Stewart

Publication date 23 September 2001

Full work available at URL http://www.elsevier.nl/cas/tree/store/disc/free/endm/store/contents.htt?jrnl=disc&sctn=endm&mode=sub&vol=3

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• scientific article; zbMATH DE number 1304325
• Approximating the bandwidth for asteroidal triple-free graphs
• Improved bandwidth approximation for trees and chordal graphs
• Hardness results for approximating the bandwidth

Cites work

• An O( n \log n ) Algorithm for Bandwidth of Interval Graphs
• Approximating the bandwidth via volume respecting embeddings
• Complexity Results for Bandwidth Minimization
• Computing the Bandwidth of Interval Graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The bandwidth problem for graphs and matrices—a survey
• The NP-completeness of the bandwidth minimization problem

Cited in

(4)

• scientific article; zbMATH DE number 1304325 (Why is no real title available?)
• An O( n \log n ) Algorithm for Bandwidth of Interval Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximating the bandwidth for asteroidal triple-free graphs

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 Q2741348)