𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating Bandwidth by Mixing Layouts of Interval Graphs

✍ Scribed by Dieter Kratsch; Lorna Stewart

Book ID
108498088
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
34 KB
Volume
3
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Computing the Bandwidth of Interval Grap
Computing the Bandwidth of Interval Graphs
✍ Kleitman, Daniel J.; Vohra, Rakesh V. πŸ“‚ Article πŸ“… 1990 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 414 KB
Interval degree and bandwidth of a graph
Interval degree and bandwidth of a graph
✍ Fedor V Fomin; Petr A Golovach πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 395 KB

The interval degree id(G) of a graph G is deΓΏned to be the smallest max-degree of any interval supergraphs of G. One of the reasons for our interest in this parameter is that the bandwidth of a graph is always between id(G)=2 and id(G). We prove also that for any graph G the interval degree of G is