×

Bandwidth of bipartite permutation graphs in polynomial time. (English) Zbl 1136.05323

Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 216-227 (2008).
Summary: We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length 2, chain graphs, cographs, and interval graphs.
For the entire collection see [Zbl 1133.68008].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Assmann, S. F.; Peck, G. W.; Sysło, M. M.; Zak, J., The bandwidth of caterpillars with hairs of length 1 and 2, SIAM J. Algebraic and Discrete Methods, 2, 387-393 (1981) · Zbl 0494.05059 · doi:10.1137/0602041
[2] Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem. Technical report, University of Bonn (1997)
[3] Blum, A.; Konjevod, G.; Ravi, R.; Vempala, S., Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems, Proceedings of STOC 1998, 100-105 (1998), New York: ACM, New York · Zbl 1028.68222
[4] Bodlaender, H. L.; Fellows, M. R.; Hallet, M. T., Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy, Proceedings of STOC 1994, 449-458 (1994), New York: ACM, New York · Zbl 1345.68152
[5] Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), New York: Springer, New York · Zbl 0961.68533
[6] Feige, U., Approximating the Bandwidth via Volume Respecting Embeddings, Proceedings of STOC 1998, 90-99 (1998), New York: ACM, New York · Zbl 1027.68650
[7] Feige, U.; Talwar, K.; Chekuri, C.; Jansen, K.; Rolim, J. D.P.; Trevisan, L., Approximating the Bandwidth of Caterpillars, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 62-73 (2005), Heidelberg: Springer, Heidelberg · Zbl 1142.05366
[8] Fishburn, P.; Tanenbaum, P.; Trenk, A., Linear discrepancy and bandwidth, Order, 18, 237-245 (2001) · Zbl 1004.06006 · doi:10.1023/A:1012267732204
[9] George, J. A.; Liu, J. W.H., Computer Solution of Large Sparse Positive Definite Systems (1981), Englewood Cliffs, New Jersey: Prentice-Hall Inc., Englewood Cliffs, New Jersey · Zbl 0516.65010
[10] Gupta, A.: Improved bandwidth approximation for trees. In: Proceedings of SODA 2000, pp. 788-793. ACM, SIAM (2000) · Zbl 0957.68086
[11] Haralambides, J.; Makedon, F.; Monien, B., Bandwidth Minimization: An Approximation Algorithm for Caterpillars, Mathematical Systems Theory, 24, 3, 169-177 (1991) · Zbl 0767.68081 · doi:10.1007/BF02090396
[12] Heggernes, P., Kratsch, D., Meister, D.: Bandwidth of bipartite permutation graphs in polynomial time. In: Reports in Informatics, University of Bergen, Norway, vol. 356 (2007) · Zbl 1136.05323
[13] Kleitman, D. J.; Vohra, R. V., Computing the bandwidth of interval graphs, SIAM J. Disc. Math., 3, 373-375 (1990) · Zbl 0704.05044 · doi:10.1137/0403033
[14] Kloks, T.; Kratsch, D.; Müller, H., Bandwidth of chain graphs, Information Processing Letters, 68, 313-315 (1998) · Zbl 1339.05393 · doi:10.1016/S0020-0190(98)00173-2
[15] Kloks, T.; Kratsch, D.; Müller, H., Approximating the bandwidth for AT-free graphs, Journal of Algorithms, 32, 41-57 (1999) · Zbl 0951.68113 · doi:10.1006/jagm.1998.0997
[16] Meister, D., Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Disc. Appl. Math., 146, 193-218 (2005) · Zbl 1077.68076 · doi:10.1016/j.dam.2004.10.001
[17] Monien, B., The bandwidth minimization problem with hair length 3 is NP-complete, SIAM J. Alg. Disc. Meth., 7, 505-512 (1986) · Zbl 0624.68059 · doi:10.1137/0607057
[18] Papadimitriou, C., The NP-completeness of the bandwidth minimization problem, Computing, 16, 263-270 (1976) · Zbl 0321.65019 · doi:10.1007/BF02280884
[19] Spinrad, J.; Brandstädt, A.; Stewart, L., Bipartite permutation graphs, Disc. Appl. Math., 18, 279-292 (1987) · Zbl 0628.05055 · doi:10.1016/S0166-218X(87)80003-3
[20] Unger, W., The Complexity of the Approximation of the Bandwidth Problem, Proceedings of FOCS 1998, 82-91 (1998), Los Alamitos: IEEE, Los Alamitos
[21] Yan, J. H., The bandwidth problem in cographs, Tamsui Oxf. J. Math. Sci., 13, 31-36 (1997) · Zbl 0903.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.