×

zbMATH — the first resource for mathematics

Topological bandwidth. (English) Zbl 0573.05052
The authors present a number of results on comparison of the topological bandwidth of a graph to other graphical invariant, such as cutwidth, modified cutwidth, search number, and node search number. For binary trees of order n, a 0(n log n) algorithm to compute their topological bandwidth is obtained. Further, it is shown that the problem, given a graph G and an integer k, whether the topological bandwidth of G is at most k is NP-complete (even when restricted to cubic graphs). It is also shown that the Min Cut Linear Arrangement problem, the Search number problem, the Modified Cutwidth problem, and the Node Search Number problem are NP-complete (even for graphs with max degree 3). Finally, graphs with topological bandwidth 2 are characterized, and an \(0(| G|^ k)\) algorithm for deciding whether the topological bandwidth of a graph G is at most k is given.
Reviewer: J.Širáň

MSC:
05C99 Graph theory
68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arany, I.; Szoda, L.; Smith, W. F., An improved method for reducing the bandwidth of sparse symmetric matrices, Information processing 71 (Proc. IFIP Congr., Ljubljana, 1971), Vol. 2: Applications, 1246, (1972), North-Holland, Amsterdam · Zbl 0259.65034
[2] Chinn, P. Z.; Chvatalova, J.; Dewdney, A. K.; Gibbs, N. E., The bandwidth problem for graphs and matrices—a survey, J. Graph Theory, 6, 223, (1982) · Zbl 0494.05057
[3] Chung, F. R. K.; Chartrand, G., Some problems and results in labelings of graphs, The theory and applications of graphs (Kalamazoo, Mich., 1980), 255, (1981), Wiley, New York · Zbl 0468.05065
[4] Chung, FanR. K., On the cutwidth and the topological bandwidth of a tree, SIAM J. Algebraic Discrete Methods, 6, 268, (1985) · Zbl 0565.05019
[5] Chung, M.-J.; Makedon, F. S.; Sudborough, I. H.; Turner, J., Polynomial time algorithms for the MIN CUT problem on degree restricted trees, SIAM J. Comput., 14, 158, (1985) · Zbl 0603.68068
[6] Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D., Complexity results for bandwidth minimization, SIAM J. Appl. Math., 34, 477, (1978) · Zbl 0385.05048
[7] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039
[8] Some NP-complete problems on graphsProc. 11th Annual Conference on Information Sciences and SystemsJohns Hopkin Univ.Baltimore, MD19779195
[9] Gurari, EitanM.; Sudborough, IvanHal, Improved dynamic programming algorithms for bandwidth minimization and the MINCUT linear arrangement problem, J. Algorithms, 5, 531, (1984) · Zbl 0556.68012
[10] Recontamination does not helpTechnical ReportDept. Computer Science, Princeton Univ.Princeton, NJ1982
[11] Lengauer, Thomas, Upper and lower bounds on the complexity of the MIN-cut linear arrangement problem on trees, SIAM J. Algebraic Discrete Methods, 3, 99, (1982) · Zbl 0489.68060
[12] Lengauer, Thomas, Black-white pebbles and graph separation, Acta Inform., 16, 465, (1981) · Zbl 0454.68027
[13] Liu, W.; Sherman, A. B., Comparative analysis of the cuthill-mckee and the reverse cuthill-mckee ordering algorithms for sparse matrices, SIAM J. Numer. Anal., 13, 198, (1976) · Zbl 0331.65022
[14] Ph.D. ThesisLayout problems and their complexityElectrical Engineering and Computer Science Dept., Northwestern Univ.Evanston, IL1982
[15] Minimizing width in linear layoutsProc 10th International Colloquium on Automata, Languages, and ProgrammingLecture Notes in Computer ScienceVol. 154Springer VerlagNew York1983478490
[16] The complexity of searching a graphProc. 22nd Annual IEEE Symposium on Foundations of Computer Science1981376385
[17] Monien, Burkhard; Sudborough, IvanHal, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Theoret. Comput. Sci., 21, 237, (1982) · Zbl 0493.68046
[18] Bandwidth constrained NP-complete problemsProc. 11th Annual ACM Symposium on Theory of Computing1981207217
[19] Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, ErnestS.; Kashiwabara, Toshinobu; Fujisawa, Toshio, One-dimensional logic gate assignment and interval graphs, IEEE Trans. Circuits and Systems, 26, 675, (1979) · Zbl 0414.94052
[20] personal communication
[21] Papadimitriou, C. H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 263, (1976) · Zbl 0321.65019
[22] Redziejowski, R. R., On arithmetic expressions and trees, Comm. ACM, 12, 81, (1969) · Zbl 0167.45804
[23] Rosenberg, A. L.; Sudborough, I. H., Bandwidth and pebbling, Computing, 31, 115, (1983) · Zbl 0509.90100
[24] Saxe, JamesB., Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM J. Algebraic Discrete Methods, 1, 363, (1980) · Zbl 0496.68032
[25] private communication to M. R. Garey and D. S. Johnson, cited in [7, p. 201]
[26] Sudborough, IvanHal, Bandwidth constraints on problems complete for polynomial time, Theoret. Comput. Sci., 26, 25, (1983) · Zbl 0535.68021
[27] On computing the width and black/ white pebble demand of treesTechnical ReportElectrical Engineering and Computer Science Dept. Northwestern Univ.Evanston1983
[28] Trimberg, S., Automating chip layout, IEEE Spectrum, 38, (1982)
[29] Weinberger, A., Large scale integration of MOS complex logic: A layout method, IEEE J. Solid State Circuits, SC-2, 182, (1967)
[30] A hueristic procedure for ordering MOS arraysProc. Design Automation Conference1975384393
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.