{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:59Z","timestamp":1725663299187},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540127277"},{"type":"electronic","value":"9783540387145"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_19","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:54:57Z","timestamp":1330192497000},"page":"317-331","source":"Crossref","is-referenced-by-count":2,"title":["Topological bandwidth"],"prefix":"10.1007","author":[{"given":"F. S.","family":"Makedon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. H.","family":"Sudborough","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"19_CR1","unstructured":"I. Arany, L. Szoda, and W.F. Smith, \"An Improved Method for Reducing the Bandwidth of Sparse Symetric Matrices\", Proc. 1971 IFIP Congress, pp. 1246\u20131250."},{"key":"19_CR2","series-title":"Technical Report","volume-title":"On the Cutwidth and the Topological Bandwidth of a Tree","author":"F. R. K. K. Chung","year":"1982","unstructured":"F.R.K. Chung, \"On the Cutwidth and the Topological Bandwidth of a Tree\", Technical Report, Bell Laboratories, Murray Hill, New Jersey, U.S.A. (1982)"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"M.-J. Chung, F. S. Makedon, I. H. Sudborough, and J. Turner, \"Polynomial Algorithms for the Min Cut Linear Arrangement Problem on Degree Restricted Trees\", Proc. 23rd Annual IEEE Foundations of Computer Science Symp. (1982)","DOI":"10.1109\/SFCS.1982.85"},{"key":"19_CR4","unstructured":"J. Chvatalova, A.K. Dewdney, N. E. Gibbs, and R. R. Khorfage, \"The Bandwidth Problem for Graphs: A Collection of Recent Results, Research Report 24, Dept. of Computer Science, University of Western Ontario, London, Ontario, Canada."},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. Garey","year":"1978","unstructured":"M. Garey, R. L. Graham, D. S. Johnson, and D. Knuth, \"Complexity Results for Bandwidth Minimization\", SIAM J. on Applied Mathematics 34 (1978), pp. 477\u2013495.","journal-title":"SIAM J. on Applied Mathematics"},{"key":"19_CR6","volume-title":"Computers and Intractability, A Guide to the Theory of NP-comleteness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-comleteness, W. H. Freeman and Co., San Francisco (1979)."},{"key":"19_CR7","first-page":"91","volume-title":"\"Some NP-complete Problems on Graphs\", Proc. 11th Annual Conf. on Info. Sciences and Systems","author":"F. Gavril","year":"1977","unstructured":"F. Gavril, \"Some NP-complete Problems on Graphs\", Proc. 11th Annual Conf. on Info. Sciences and Systems, The Johns Hopkins University, Baltimore, Md., U.S.A. (1977), pp. 91\u201395."},{"key":"19_CR8","unstructured":"E. M. Gurari and I. H. Sudborough, \"Improved Dynamic Programming Algorithms for the Bandwidth Minimization Problem and the Min Cut Linear Arrangement problem\", Technical Report, Dept. of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60201 U. S. A. (1981)."},{"key":"19_CR9","series-title":"Technical Report","volume-title":"Recontamination Does Not Help","author":"A. LaPaugh","year":"1982","unstructured":"A. LaPaugh, \"Recontamination Does Not Help\", Technical Report, Princeton University, Princeton, New Jersey, U. S. A. (1982)."},{"key":"19_CR10","series-title":"Technical Report","volume-title":"Upper and Lower Bounds on the Complexity of the Min Cut Linear Arrangement Problem on Trees","author":"T. Lengauer","year":"1980","unstructured":"T. Lengauer, \"Upper and Lower Bounds on the Complexity of the Min Cut Linear Arrangement Problem on Trees\", Technical Report TM-80-1272-9, Bell Laboratories, Murray Hill, New Jersey, U. S. A. (1980)."},{"key":"19_CR11","series-title":"Technical Report","volume-title":"Black-White Pebbles and Graph Separation","author":"T. Lengauer","year":"1980","unstructured":"T. Lengauer, \"Black-White Pebbles and Graph Separation\", Technical Report, Bell Laboratories, Murray Hill, New Jersey, U.S.A. (1980)."},{"key":"19_CR12","unstructured":"W. Loui and A.B. Sherman, \"Comparative Analysis of the Cuthill-McKee Ordering Algorithms for Sparse Matrices\", SIAM J. Numerical Analysis (1976)."},{"key":"19_CR13","volume-title":"Layout Problems and Their Complexity","author":"F. Makedon","year":"1982","unstructured":"F. Makedon, Layout Problems and Their Complexity, Ph. D. Thesis, Electrical Engineering and Computer Science Dept., Northwestern University, Evanston, IL U.S.A. (1982)."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"N. Megiddo, L. Hakimi, M.R. Garey, D. S. Johnson, and C. H. Papadimitriou, \"The Complexity of Searching a Graph\", Proc. 22nd Annual IEEE Foundations of Computer Science Symp. (1981), pp. 376\u2013385.","DOI":"10.1109\/SFCS.1981.46"},{"key":"19_CR15","unstructured":"B. Monien and I. H. Sudborough, \"On Eliminating Nondeterminism from Turing Machines that Use Less than Logarithm Space\", to appear in Theoretical Computer Science."},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"B. Monien and I. H. Sudborough, \"Bandwidth Constrained NP-Complete Problems\", Proc. 11th Annual ACM Theory of Computer Science SYmp. (1981), pp. 207\u2013217.","DOI":"10.1145\/800076.802474"},{"key":"19_CR17","unstructured":"C. H. Papadimitriou and L. Kyrousis, work in progress."},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF02280884","volume":"16","author":"C. H. Papadimitriou","year":"1976","unstructured":"C. H. Papadimitriou, \"The NP-Completeness of the Bandwidth Minimization Problem\", Computing 16 (1976), pp. 237\u2013267.","journal-title":"Computing"},{"key":"19_CR19","unstructured":"A. L. Rosenberg and I. H. Sudborough, \"Bandwidth and Pebbling\", to appear in Computing."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"J. B. Saxe, \"Dynamic Programming Algorithms for Recognizing Small Bandwidth Graphs in Polynomial Time\", SIAM J. Algebraic and Discrete Methods (1980).","DOI":"10.1137\/0601042"},{"key":"19_CR21","unstructured":"L. J. Stockmeyer, private communication to M. R. Garey and D. S. Johnson, cited in Computers and Intractability, A Guide to the Theory of NP-Completeness, see [6], p. 201."},{"key":"19_CR22","unstructured":"I. H. Sudborough, \"Bandwidth Constraints on Problems Complete for Polynomial Time\", to appear in Theoretical Computer Science."},{"key":"19_CR23","unstructured":"I. H. Sudborough and J. Turner, \"On Computing the Width and Black\/White Pebble Demand of Trees\", work in progress."}],"container-title":["Lecture Notes in Computer Science","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:12Z","timestamp":1605643572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}