×

Bandwidth and topological bandwidth of graphs with few \(P_4\)’s. (English) Zbl 0989.05104

Summary: We give a polynomial time algorithm to compute the bandwidth of a \((q,q- 4)\)-graph for each constant \(q\). We show also that the bandwidth and topological bandwidth of \(P_4\)-sparse graphs are equal. Let \(H\) be a subdivision of a graph \(G\) with a minimal number of vertices such that the bandwidth of \(H\) equals the topological bandwidth of \(G\). We show that the number of vertices of \(H\) is \(O(n^3)\), where \(n\) is the number of vertices in \(G\), and thus the topological bandwidth of a graph of constant size can be computed in constant time.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C35 Extremal problems in graph theory
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 Discrete Methods, 2, 387-393 (1981) · Zbl 0494.05059
[2] L. Babel, On the \(P_4\)-structure of graphs, Habilitationsschrift, Zentrum für Mathematik, Technische Universität München, 1997.; L. Babel, On the \(P_4\)-structure of graphs, Habilitationsschrift, Zentrum für Mathematik, Technische Universität München, 1997.
[3] L. Babel, T. Kloks, J. Kratochvı́l, D. Kratsch, H. Müller, S. Olariu, Efficient algorithms for graphs with few \(P_4\)’s, Manuscript 1998.; L. Babel, T. Kloks, J. Kratochvı́l, D. Kratsch, H. Müller, S. Olariu, Efficient algorithms for graphs with few \(P_4\)’s, Manuscript 1998.
[4] S. Baumann, A linear algorithm for the homogeneous decomposition of graphs, Report No. M-9615, Zentrum für Mathematik, Technische Universität München, 1996.; S. Baumann, A linear algorithm for the homogeneous decomposition of graphs, Report No. M-9615, Zentrum für Mathematik, Technische Universität München, 1996.
[5] H. Bodlaender M.R. Fellows, M.T. Hallet, Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy, Proceedings of the 26th Annual Symposium on the Theory of Computation, 1994, pp. 449-458.; H. Bodlaender M.R. Fellows, M.T. Hallet, Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy, Proceedings of the 26th Annual Symposium on the Theory of Computation, 1994, pp. 449-458. · Zbl 1345.68152
[6] Brandstädt, A.; Le, V. B.; Spinrad, J., Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM: SIAM Philadelphia
[7] Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E., The bandwidth problem for graphs and matrices—a survey, J. Graph Theory, 6, 223-254 (1982) · Zbl 0494.05057
[8] F.R.K. Chung, Labelings of graphs, in: Selected Topics in Graph Theory, Vol. 3, Academic Press, London, 1988, pp. 151-168.; F.R.K. Chung, Labelings of graphs, in: Selected Topics in Graph Theory, Vol. 3, Academic Press, London, 1988, pp. 151-168.
[9] U. Feige, Approximating the bandwidth via volume respecting embeddings, Manuscript, 1998.; U. Feige, Approximating the bandwidth via volume respecting embeddings, Manuscript, 1998. · Zbl 1027.68650
[10] Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E., Complexity results for bandwidth minimization, SIAM J. Appl. Math., 34, 477-495 (1978) · Zbl 0385.05048
[11] Giakoumakis, V.; Roussel, F.; Thuillier, H., On \(P_4\)-tidy graphs, Discrete Math. Theoret. Comput. Sci., 1, 17-41 (1997) · Zbl 0930.05073
[12] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[13] Gurari, E.; Sudborough, I. H., Improved dynamic programming algorithms for the bandwidth minimization and the mincut linear arrangement problem, J. Algorithms, 5, 531-546 (1984) · Zbl 0556.68012
[14] W. Hochstättler, G. Tinhofer, Hamiltonicity in graphs with few \(P_4\)’s, Computing 54 (1995) 213-225.; W. Hochstättler, G. Tinhofer, Hamiltonicity in graphs with few \(P_4\)’s, Computing 54 (1995) 213-225.
[15] Jamison, B.; Olariu, S., On a tree representation for \(P_4\)-extendible graph, Discrete Appl. Math., 34, 151-164 (1991) · Zbl 0754.05051
[16] Jamison, B.; Olariu, S., A tree representation for \(P_4\)-sparse graphs, Discrete Appl. Math., 35, 115-129 (1992) · Zbl 0763.05092
[17] Jamison, B.; Olariu, S., Recognizing \(P_4\)-sparse graphs in linear time, SIAM J. Comput., 21, 381-406 (1992) · Zbl 0763.05093
[18] Jamison, B.; Olariu, S., Linear time optimization algorithms for \(P_4\)-sparse graphs, Discrete Appl. Math., 61, 155-175 (1995) · Zbl 0831.68075
[19] Jamison, B.; Olariu, S., \(p\)-components and the homogeneous decomposition of graphs, SIAM J. Discrete Math., 8, 448-463 (1995) · Zbl 0830.05056
[20] S. Jiang, The bandwidth problem and bandwidth of cographs. Manuscript, 1992.; S. Jiang, The bandwidth problem and bandwidth of cographs. Manuscript, 1992.
[21] Kaplan, H.; Shamir, R., Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques, SIAM J. Comput., 25, 540-561 (1996) · Zbl 0852.68072
[22] Kleitman, D. J.; Vohra, R. V., Computing the bandwidth of interval graphs, SIAM J. Discrete Math., 3, 373-375 (1990) · Zbl 0704.05044
[23] T. Kloks, D. Kratsch, H. Müller, Approximating the bandwidth for AT-free graphs, Proceedings of the Third Annual European Symposium on Algorithms (ESA’95), Springer, Lecture Notes in Computer Science, Vol. 979, 1995, pp. 434-447.; T. Kloks, D. Kratsch, H. Müller, Approximating the bandwidth for AT-free graphs, Proceedings of the Third Annual European Symposium on Algorithms (ESA’95), Springer, Lecture Notes in Computer Science, Vol. 979, 1995, pp. 434-447.
[24] T. Kloks, D. Kratsch, H. Müller, Bandwidth of chain graphs, KAM-DIMATIA Series, 98-390, Centre for Discrete Mathematics, Theoretical Computer Science and Applications (DIMATIA), Charles University, Prague, Czech Republic, 1998.; T. Kloks, D. Kratsch, H. Müller, Bandwidth of chain graphs, KAM-DIMATIA Series, 98-390, Centre for Discrete Mathematics, Theoretical Computer Science and Applications (DIMATIA), Charles University, Prague, Czech Republic, 1998.
[25] Mahesh, R.; Rangan, C. P.; Srinivasan, A., On finding the minimum bandwidth of interval graphs, Inform. and Comput., 95, 218-224 (1991) · Zbl 0738.68046
[26] Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H., Topological bandwidth, SIAM J. Algebraic Discrete Methods, 6, 418-444 (1985) · Zbl 0573.05052
[27] Monien, B., The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM J. Algebraic Discrete Methods, 7, 505-512 (1986) · Zbl 0624.68059
[28] Papadimitriou, C. H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 263-270 (1976) · Zbl 0321.65019
[29] Peck, G. W.; Shastri, A., Bandwidth of theta graphs with short paths, Discrete Math., 103, 177-187 (1992) · Zbl 0761.05084
[30] Sprague, A. P., An \(O(n log n)\) algorithm for bandwidth of interval graphs, SIAM J. Discrete Math., 7, 213-220 (1994) · Zbl 0797.05070
[31] W. Unger, The complexity of the approximation of the bandwidth problem. Proceedings of FOCS’98, pp. 82-91.; W. Unger, The complexity of the approximation of the bandwidth problem. Proceedings of FOCS’98, pp. 82-91.
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.