zbMATH — the first resource for mathematics

Routing with critical paths. (English) Zbl 0695.68045
Summary: Given an undirected graph, a set of simple paths in the graph and a bound for each path, we wish to know whether the vertices of the graph can be laid out on a line so that each path is stretched no more than its bound. The problem is solvable in polynomial time for fixed bounds and path lengths.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
90C39 Dynamic programming
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Bhatt, S.; Chung, F.R.K.; Leighton, T.; Rosenberg, A.L., Optimal simulations of tree machines, Proc. IEEE FOCS symposium, 274-282, (1986)
[2] Chung, F.R.K., On optimal linear arrangement of trees, Comput. math. appl., 10, 1, 43-60, (1984) · Zbl 0533.05022
[3] Chung, F.R.K.; Leighton, T.; Rosenberg, A.L., Embedding graphs in books: A layout problem with applications to VLSI design, SIAM J. algebraic discrete methods, 8, 33-58, (1987) · Zbl 0617.68062
[4] Ellis, J., Embedding graphs in lines, trees and grids, ()
[5] 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
[6] Garey, M.R.; Johnson, D.S.; Stockmeyer, L.J., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[7] Gurari, E.; Sudborough, I.H., Improved dynamic programming algorithms for bandwidth minimization and the MIN-cut linear arrangement problem, J. algorithms, 5, 531-546, (1984) · Zbl 0556.68012
[8] Heath, L.S.; Rosenberg, A.L.; Smith, B.T., The physical mapping problem for parallel architectures, J. ACM, 35, 603-634, (1988)
[9] Makedon, F., Layout problems and their complexity, () · Zbl 1111.68330
[10] Ohtsuki, T.; Mori, H.; Kuh, E.S.; Kashiwabara, T.; Fujisawa, T., One dimensional logic gate assignment and interval graphs, IEEE trans. circuits and systems, 26, 9, 675-684, (1979) · Zbl 0414.94052
[11] Simonson, S., Layout problems on trees, ()
[12] Simonson, S., A variation on the MIN cut linear arrangement problem, Math. systems theory, 20, 235-252, (1987) · Zbl 0643.68094
[13] Yannakakis, M., A polynomial time algorithm for the MIN cut linear arrangement of trees, J. ACM, 32, 4, 950-988, (1985) · Zbl 0633.68063
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.