𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On finding the minimum bandwidth of interval graphs

✍ Scribed by R. Mahesh; C.Pandu Rangan; Aravind Srinivasan

Book ID
113383983
Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
348 KB
Volume
95
Category
Article
ISSN
0890-5401

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
On minimum intersection of two minimum d
On minimum intersection of two minimum dominating sets of interval graphs
✍ Chang Maw-Shang; Hsu Chung-Chang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 748 KB

This paper gives linear-time algorithms for finding two minimum (connected) dominating sets with minimum intersection for interval graphs.

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