{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:34:30Z","timestamp":1766378070788},"reference-count":30,"publisher":"EDP Sciences","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1995]]},"DOI":"10.1051\/ita\/1995290604871","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:15:20Z","timestamp":1486048520000},"page":"487-508","source":"Crossref","is-referenced-by-count":10,"title":["On bandwidth, cutwidth, and quotient graphs"],"prefix":"10.1051","volume":"29","author":[{"given":"Dominique","family":"Barth","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Pellegrini","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Raspaud","sequence":"additional","affiliation":[]},{"given":"Jean","family":"Roman","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","unstructured":"1. BARTH D., R\u00e9seaux d'interconnexion : Structures et Communications, Th\u00e8se de Doctorat, LaBRI, Universit\u00e9 Bordeaux-I, 351 cours de la Lib\u00e9ration, 33405 Talence, France, janvier 1994."},{"key":"R2","unstructured":"2. BARTH D., PELLEGRINI F., RASPAUD A. and ROMAN J., On Bandwidth, Cutwidth, and Quotient graphs, Research report 814-94, LaBRI, Universit\u00e9 Bordeaux-I, 351 cours de la Lib\u00e9ration, 33405 Talence, France, mars 1994."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. BEL HALA A., Congestion optimale du plongement de l'hypercube H (n) dans la cha\u00eene P (2n), Rairo Informatique Th\u00e9orique et Applications, 1993, 27 (4), pp. 1-17.924610803.68091","DOI":"10.1051\/ita\/1993270504651"},{"key":"R4","unstructured":"4. BEL HALA A., Communications dans les r\u00e9seaux d'interconnexion : plongements optimaux de l'hypercube. Th\u00e8se de Doctorat, LaBRI, Universit\u00e9 Bordeaux-I, 351 cours de la Lib\u00e9ration, 33405 Talence, France, janvier 1995."},{"key":"R5","unstructured":"5. BERGE C., Graphs and Hypergraphs, North Holland Publishing, 1973.0254.05101"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. CHINN P. Z., CHV\u00c0TALOV\u00c0 J., DEWDNEY A. K. and GIBBS N. E., The Bandwidth Problem for Graphs and Matrices, A survey, Journal of Graph Theory, 1982, 6, pp. 223-254.6667940494.05057","DOI":"10.1002\/jgt.3190060302"},{"key":"R7","unstructured":"7. CHUNG F. R. K., The Theory and Applications of Graphs, chapter Some Problems and Results in Labelling of Graphs, pp. 255-263, John Wiley, 1981.6345310468.05065"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"8. FELDMANN R. and UNGER W., The Cube-Connected Cycles network is a subgraph of the Butterfly network, Parallel Processing Letters, 1992, 2 (1), pp. 13-19.","DOI":"10.1142\/S0129626492000131"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. FELLER A., Automatic layout of low-cost quick-turnaround random-logic customs LSI devices, In Proc. 13th Design Automation Conf., pp. 79-85, San Francisco, 1976.","DOI":"10.1145\/800146.804799"},{"key":"R10","unstructured":"10. GAREY M. R. and JOHNSON D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979.5190660411.68039"},{"key":"R11","unstructured":"11. GAVRIL F., Some NP-complete problems on graphs, In Proc. 11th conference on information sciences and Systems, pp. 91-95, John Hopkins University, Baltimore."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"12. GIBBS N. E., POOLE W. G. and STOCKMEYER P. K., A comparison of several bandwidth and profile reduction algorithms, ACM Trans. Math. Software, 1976, 2, pp. 322-330.0345.65014","DOI":"10.1145\/355705.355707"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"13. GURARI E. M. and SUDBOROUGH I. H., Improved dynamic algorithms for bandwidth minimization and the mincut linear arrangement problem, Journal of Algorithms, 1984, 5, pp. 531-546.7699810556.68012","DOI":"10.1016\/0196-6774(84)90006-3"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"14. HARPER L. H., Optimal assignement of number of vertices, J. SIAM, 1964, 12, pp. 131-135.0222.94004","DOI":"10.1137\/0112012"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"15. HARPER L. H., Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1966, 1, pp. 385-393.2001920158.20802","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"16. KOCK R., LEIGHTON T., MAGGS B., RAO S. and ROSENBERG A., Work-preserving emulations of fixed-connection networks, In Proc. 21st Annual Symposium on Theory of Computing, pp. 227-240, ACM, 1989.","DOI":"10.1145\/73007.73029"},{"key":"R17","unstructured":"17. LAI T. H. and SPRAGUE A. S., Placement of the processors of a hypercube, Technical report, 1988."},{"key":"R18","unstructured":"18. LEIGHTON F. T., Complexity issues in VLSI. Optimal layouts for the shuffle exchange graph and other networks, in Foundations of Computing Series, The MIT press, 1983."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"19. LEIGHTON F. T., Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes, Morgan Kaufman Publisher, 1992.11372720743.68007","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"20. MONIEN B. and SUDBOROUGH H., Embedding one interconnection network in another, Computing Supplements, 1990, 7, pp. 257-282.10599340699.68017","DOI":"10.1007\/978-3-7091-9076-0_13"},{"key":"R21","unstructured":"21. NAKANO K., CHEN W., MASUZAWA T., HAGIHARA K. and TOKURA N., Cut width and bisection width of hypercube graph, IEICE Transactions, J73-A, (4), pp. 856-862, april 1990, In Japanese."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"22. PAPADIMITRIOU C. H., The NP-completeness of the bandwidth minimization problem, Computing, 1976, 16, pp. 263-270.4112430321.65019","DOI":"10.1007\/BF02280884"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"23. PELLEGRINI F., Bounds for the bandwidth of the d-ary de Bruijn graph, Parallel Processing Letters. Special Number on Interconnection Networks, 1993, 3 (4), pp. 431-443.","DOI":"10.1142\/S0129626493000460"},{"key":"R24","unstructured":"24. PELLEGRINI F., Application de m\u00e9thodes de partition \u00e0 la r\u00e9solution de probl\u00e8mes de graphes issus du parall\u00e9lisme, Th\u00e8se de Doctorat, LaBRI, Universit\u00e9 Bordeaux-I, 351 cours de la Lib\u00e9ration, 33405 Talence, France, janvier 1995."},{"key":"R25","unstructured":"25. PERSKY G., DEUTSCH D. and SCHWEIKERT D., LTX-A minicomputer-based system for automated LSI layout, J. Design Automation and Fault Tolerant Computing, 1977, 1, pp. 217-255."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"26. PREPARATA F. and VUILLEMIN J., The Cube-Connected Cycles: a versatile network for parallel computation, Communications of the ACM, May 1981, 24 (5), pp. 300-309.614176","DOI":"10.1145\/358645.358660"},{"key":"R27","unstructured":"27. SHAHROKHI F. and SZEKELY L. A., An algebraic approach to the uniform concurrent multicommodity flow. Theory and applications, Technical Report CRPDC-91-4, University of North Texas, 1991."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"28. SMITH W. F. and ARANY I., Another algorithm for reducing bandwidth and profile of a sparse matrix, In Proc. AFIPS 1976 NCC, pp. 341-352, Montvale, New Jersey, 1976, AFIP Press.","DOI":"10.1145\/1499799.1499935"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"29. TRIMBERG S., Automating chip layout, IEEE Spectrum, pp. 38-45, 1982.","DOI":"10.1109\/MSPEC.1982.6366725"},{"key":"R30","unstructured":"30. YOSHIZAWA H., KAWANISHI H. and KANI K., A heuristic procedure for ordering MOS arrays, In Proc. of Design Automation Conference, pp. 384-393, 1975."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1995290604871\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T06:00:56Z","timestamp":1568786456000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1995290604871"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"references-count":30,"journal-issue":{"issue":"6"},"alternative-id":["ita1995290604871"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1995290604871","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}