scientific article

zbMath1039.05535MaRDI QIDQ2741348

Dieter Kratsch, Lorna K. 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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Cites Work

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