| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427733 | Information Processing Letters | 2012 | 7 Pages |
Abstract
We show that the bandwidth problem is NP-complete for convex bipartite graphs. We provide an O(n)-time, 4-approximation algorithm and an -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 -time, 3-approximation algorithm, where n is the number of vertices.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
