Bandwidth of chain graphs

We show that there is an O( n 2 log n) algorithm to compute the bandwidth of a chain graph. Here n is the number of vertices in the graph.

Saved in:
Bibliographic Details
Published in:Information processing letters 1998-12, Vol.68 (6), p.313-315
Main Authors: Kloks, Ton, Kratsch, Dieter, Müller, Haiko
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Bandwidth
Chain graphs
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph algorithms
Graph theory
Graphs
Information processing
Information retrieval. Graph
Mathematics
Sciences and techniques of general use
Studies
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that there is an O( n 2 log n) algorithm to compute the bandwidth of a chain graph. Here n is the number of vertices in the graph.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(98)00173-2