Bandwidth of convex bipartite graphs and related graphs

We show that the bandwidth problem is NP-complete for convex bipartite graphs. We provide an O(n)-time, 4-approximation algorithm and an O(nlog2n)-time, 2-approximation algorithm to compute the bandwidth of convex bipartite graphs with n vertices. We also consider 2-directional orthogonal ray graphs...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2012-06, Vol.112 (11), p.411-417
Main Authors: Shrestha, Anish Man Singh, Tayu, Satoshi, Ueno, Shuichi
Format: Article
Language:English
Subjects:
(Bi)convex bipartite graphs
2-Directional orthogonal ray graphs
Algorithms
Approximation
Approximation algorithms
Bandwidth
Bandwidth problem
Bandwidths
Binary system
Codes
Data processing
Graph theory
Graphs
Studies
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 the bandwidth problem is NP-complete for convex bipartite graphs. We provide an O(n)-time, 4-approximation algorithm and an O(nlog2n)-time, 2-approximation algorithm to compute the bandwidth of convex bipartite graphs with n vertices. We also consider 2-directional orthogonal ray graphs, a superclass of convex bipartite graphs, for which we provide an O(n2logn)-time, 3-approximation algorithm, where n is the number of vertices.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2012.02.012