Computing the Bandwidth of Interval Graphs
- 1 August 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 3 (3), 373-375
- https://doi.org/10.1137/0403033
Abstract
Summary:In this paper, we improve the result by Harper on the lower bound of the bandwidth of connected graphs. In addition, we prove that considerating the interior boundary and the exterior boundary when estimating the bandwidth of connected graphs gives the same resultsKeywords
This publication has 6 references indexed in Scilit:
- Finding the minimum bandwidth of an interval graphInformation and Computation, 1987
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1986
- The NP-completeness column: an ongoing guideJournal of Algorithms, 1985
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- The NP-Completeness of the bandwidth minimization problemComputing, 1976
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962