Optimal labelling of unit interval graphs

DOI10.1007/BF02662875MaRDI QIDQ1906576zbMATH OpenFDO

Authors Jinjiang Yuan, Sanming Zhou

Publication date 4 July 1996

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02662875

zbMATH Keywords

bandwidthbandwidth sumcutwidthcyclic bandwithlabellingsunit interval graph

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

After having given the definitions of the 7 different labellings called bandwidth labelling, cyclic bandwith labelling, profile labelling, fill-in labelling, cutwidth labelling, modified cutwidth labelling, and bandwidth sum labelling, the two authors show for every unit interval graph the existence of a labelling that is simultaneously optimal for the 7 labellings mentioned above.

Recommendations

• On distance two labelling of unit interval graphs
• scientific article; zbMATH DE number 4070955
• scientific article; zbMATH DE number 7081025
• scientific article; zbMATH DE number 4075107
• Optimal distance labeling for interval and circular-arc graphs

Cites work

• Computing the Minimum Fill-In is NP-Complete
• scientific article; zbMATH DE number 719423 (Why is no real title available?)
• Profile minimization problem for matrices and graphs
• Topological Bandwidth
• Triangulated graphs and the elimination process

Cited in

(9)

• Embedding ray intersection graphs and global curve simplification
• On cutwidth parameterized by vertex cover
• Computing the cutwidth of bipartite permutation graphs in linear time
• Tabu search for the cyclic bandwidth problem
• Lower and upper bounds for the linear arrangement problem on interval graphs
• On cutwidth parameterized by vertex cover
• Efficient iterated greedy for the two-dimensional bandwidth minimization problem
• Maximum cut on interval graphs of interval count four is NP-complete
• Semi-proper interval graphs

This page was built for publication: Optimal labelling of unit interval graphs

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