{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T16:40:03Z","timestamp":1733503203212,"version":"3.30.1"},"reference-count":98,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,5,1]],"date-time":"2000-05-01T00:00:00Z","timestamp":957139200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4825,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,5]]},"DOI":"10.1016\/s0304-3975(98)00226-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:38:29Z","timestamp":1027651109000},"page":"31-80","source":"Crossref","is-referenced-by-count":0,"title":["Generating irregular partitionable data structures"],"prefix":"10.1016","volume":"238","author":[{"given":"Prakash","family":"Panangaden","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clark","family":"Verbrugge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/S0304-3975(98)00226-6_BIB1","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/S0895480191198768","article-title":"Planar separators","volume":"7","author":"Alon","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB2","doi-asserted-by":"crossref","unstructured":"M. Andries, G. Engels, Syntax and semantics of hybrid database languages, in: H.J. Schneider, H. Ehrig (Eds.), Graph Transformations in Computer Science: Proc. Int. Workshop, Lecture Notes in Computer Science, vol. 776, Dagstuhl Castle, Germany, Springer, Berlin, January 1993, pp. 19\u201336.","DOI":"10.1007\/3-540-57787-4_2"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB3","unstructured":"M. Andries, J. Paredaens, A language for generic graph-transformations, in: G. Schmidt, R. Berghammer (Eds.), Graph-Theoretic Concepts in Computer Science: Proc. 17th Int. Workshop, WG \u201991, Lecture Notes in Computer Science, vol. 570, Fischbachau, Germany, 17\u201319 June, Springer, Berlin, 1991, pp. 63\u201374."},{"issue":"1","key":"10.1016\/S0304-3975(98)00226-6_BIB4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","article-title":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2013 a survey","volume":"25","author":"Arnborg","year":"1985","journal-title":"BIT"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB5","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, D. Seese, Problems easy for tree-decomposable graphs, in: T. Lepist\u00f6, A. Salomaa (Eds.), Proc. 15th Int. Colloquium On Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Tampere, Finland, 11\u201315 July, Springer, Berlin, pp. 38\u201351. Extended abstract.","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB6","doi-asserted-by":"crossref","unstructured":"H.P. Barendregt, M.C.J.D. van Eekelen, J.R.W. Glauert, J.R. Kennaway, M.J. Plasmeijer, M.R. Sleep, Towards and intermediate language based on graph rewriting, in: J.W. de Bakker, A.J. Nijman, P.C. Treleaven (Eds.), Proc. PARLE \u2013 Parallel Architectures and Languages Europe, Lecture Notes in Computer Science 258\u2013259, vol. I, Eindhoven, The Netherlands, 15\u201319 June, Springer, Berlin, 1987, pp. 159\u2013174.","DOI":"10.1007\/3-540-17945-3_9"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB7","unstructured":"K. Barthelmann, G. Schied, Graph-grammar semantics of a higher-order programming language for distributed systems, in: H.J. Schneider, H. Ehrig (Eds.), Graph Transformations in Computer Science: Proc. Int. Workshop, Lecture Notes in Computer Science, vol. 776, Dagstuhl Castle, Germany, January, Springer, Berlin, 1993, pp. 71\u201385."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB8","doi-asserted-by":"crossref","unstructured":"P. Boehm, H. Ehrig, U. Hummert, M. L\u00f6we, Towards distributed graph grammars, in: H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld (Eds.), Proc. 3rd Int. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Warrenton, Virginia, 2\u20136 December, Springer, Berlin, 1986, pp. 86\u201398.","DOI":"10.1007\/3-540-18771-5_47"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB9","doi-asserted-by":"crossref","unstructured":"G.H. Botorog, H. Kuchen, Algorithmic skeletons for adaptive multigrid methods, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Int. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136, September, Springer, Berlin, 1995, pp. 27\u201341.","DOI":"10.1007\/3-540-60321-2_2"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB10","doi-asserted-by":"crossref","unstructured":"F.J. Brandenburg, The computational complexity of certain graph grammars, in: A.B. Cremers, H.P. Kriegel (Eds.), Theoretical Computer Science: 6th GI-Conf., Lecture Notes in Computer Science, vol. 145, Dortmund, West Germany, January, Springer, Berlin, 1983, pp. 91\u201399.","DOI":"10.1007\/BFb0036472"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB11","doi-asserted-by":"crossref","unstructured":"F.J. Brandenburg, On partially ordered graph grammars, in: H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld (Eds.), Proc. 3rd Int. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Warrenton, Virginia, 2\u20136 December, Springer, Berlin, 1986, pp. 99\u2013111.","DOI":"10.1007\/3-540-18771-5_48"},{"issue":"2","key":"10.1016\/S0304-3975(98)00226-6_BIB12","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1137\/0221016","article-title":"Partitioning planar graphs","volume":"21","author":"Bui","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB13","first-page":"195","article-title":"Graph rewriting","volume":"vol. B","author":"Courcelle","year":"1990"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","article-title":"An axiomatic definition of context-free rewriting and its application to NLC graph grammars","volume":"55","author":"Courcelle","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB15","doi-asserted-by":"crossref","unstructured":"B. Courcelle, The logical expression of graph properties (abstract), in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Int. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 38\u201340.","DOI":"10.1007\/BFb0017376"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB16","doi-asserted-by":"crossref","unstructured":"B. Courcelle, J. Engelfriet, G. Rozenberg, Context-free handle-rewriting hypergraph grammars, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Int. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 253\u2013268.","DOI":"10.1007\/BFb0017394"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB17","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","article-title":"Handle-rewriting hypergraph grammars","volume":"46","author":"Courcelle","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB18","doi-asserted-by":"crossref","unstructured":"A. Das, L.E. Moser, P.M. Melliar-Smith, A parallel processing paradigm for irregular applications, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Int. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 249\u2013254.","DOI":"10.1007\/3-540-60321-2_20"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB19","doi-asserted-by":"crossref","unstructured":"R. Diekmann, R. L\u00fcling, B. Monien, C. Spr\u00e4ner, A parallel local-search algorithm for the k-partitioning problem, Proc. 28th Hawaii Int. Conf. on System Sciences (HICSS \u201995), vol. 2, 1995, pp. 41\u201350.","DOI":"10.1109\/HICSS.1995.375478"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB20","doi-asserted-by":"crossref","unstructured":"R. Diekmann, D. Meyer, B. Monien, Parallel decomposition of unstructured fem-meshes, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Int. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 199\u2013215.","DOI":"10.1007\/3-540-60321-2_17"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB21","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1006\/jagm.1993.1013","article-title":"Edge separators of planar and outerplanar graphs with applications","volume":"14","author":"Diks","year":"1993","journal-title":"J. Algorithms"},{"issue":"5","key":"10.1016\/S0304-3975(98)00226-6_BIB22","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","article-title":"Lower bounds for the partitioning of graphs","volume":"17","author":"Donat","year":"1973","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB23","doi-asserted-by":"crossref","unstructured":"F. Drewes, H.J. Kreowski, A note on hyperedge replacement, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 1\u201311.","DOI":"10.1007\/BFb0017373"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB24","doi-asserted-by":"crossref","unstructured":"H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Int. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990.","DOI":"10.1007\/BFb0017372"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB25","doi-asserted-by":"crossref","unstructured":"H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld (Eds.), Proc. 3rd Int. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Warrenton, Virginia, 2\u20136 December, Springer, Berlin 1986.","DOI":"10.1007\/3-540-18771-5"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB26","doi-asserted-by":"crossref","unstructured":"H. Ehrig, Tutorial introduction to the algebraic approach of graph grammars, in: H. Ehrig, M. Nagl, G. Rozenberg, A. Rozenberg (Eds.), Proc. 3rd Internat. Workshop on Graph-Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Springer, Berlin, December 1987, pp. 3\u201314.","DOI":"10.1007\/3-540-18771-5_40"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB27","doi-asserted-by":"crossref","unstructured":"H. Ehrig, P. Boehm, U. Hummert, M. L\u00f6we, Distributed parallelism of graph transformations, in: H. Gottler, H.J. Schneider (Eds.), Proc. 13th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201987), Lecture Notes in Computer Science, vol. 314, Springer, Berlin, July 1988, pp. 1\u201319.","DOI":"10.1007\/3-540-19422-3_1"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB28","doi-asserted-by":"crossref","unstructured":"H. Ehrig, M. Korff, M. L\u00f6we, Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u2013March, Springer, Berlin, 1990, pp. 24\u201337.","DOI":"10.1007\/BFb0017375"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB29","unstructured":"H. Ehrig, M. Magl, G. Rozenberg (Eds.), Proc. 2nd Int. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, Haus Ohrbeck, West Germany, 4\u20138 October, Springer, Berlin, 1982."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB30","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0022-0000(90)90002-3","article-title":"Boundary graph grammars with dynamic edge relabeling","volume":"40","author":"Engelfriet","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB31","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, Context-free NCE graph grammars, in J. Csirik, J. Demetrovics, F. G\u00e9cseg (Eds.), Proce. Internat. Conference on Fundamentals of Computation Theory (FCT \u201989), Lecture Notes in Computer Science, vol. 532, Szeged, Hungary, August, Springer, Berlin, 1989, pp. 148\u2013161.","DOI":"10.1007\/3-540-51498-8_15"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB32","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, A characterization of context-free NCE graph languages by monadic second-order logic on trees, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, 311\u2013327.","DOI":"10.1007\/BFb0017397"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB33","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/S0022-0000(05)80022-4","article-title":"Hypergraph languages of bounded degree","volume":"48","author":"Engelfriet","year":"1994","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB34","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, G. Rozenberg, Graph grammars based on node rewriting: an introduction to NLC graph grammars, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 12\u201321.","DOI":"10.1007\/BFb0017374"},{"issue":"5","key":"10.1016\/S0304-3975(98)00226-6_BIB35","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/0045-7949(88)90004-1","article-title":"A simple and efficient automatic FEM domain decomposer","volume":"28","author":"Farhat","year":"1988","journal-title":"Comput. Struct."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB36","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230200205","article-title":"A class of bounded approximation algorithms for graph partitioning","volume":"20","author":"Feo","year":"1990","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB37","doi-asserted-by":"crossref","unstructured":"A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Internat. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995.","DOI":"10.1007\/3-540-60321-2"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB38","doi-asserted-by":"crossref","unstructured":"C.M. Fiduccia, R.M. Mattheyses, A linear-time heuristic for improving network partitions, 19th IEEE Design Automation Conf., 1982, pp. 175\u2013181.","DOI":"10.1145\/800263.809204"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB39","doi-asserted-by":"crossref","unstructured":"P. Fitzhorn, A linguistic formalism for engineering solid modeling, in: H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld (Eds.), Proc. 3rd Internat. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Warrenton, Virginia, 2\u20136 December, Springer, Berlin, 1986, pp. 202\u2013215.","DOI":"10.1007\/3-540-18771-5_54"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB40","doi-asserted-by":"crossref","unstructured":"A.L. Furtado, P.A.S. Veloso, Specification of data bases through rewriting rules, in: H. Ehrig, M. Magl, G. Rozenberg (Eds.), Proc. 2nd Internat. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, Haus Ohrbeck, West Germany, 4\u20138 October, Springer, Berlin, 1982, pp. 102\u2013114.","DOI":"10.1007\/BFb0000101"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB41","doi-asserted-by":"crossref","unstructured":"T. Gautier, J.L. Roch, G. Villard, Regular versus irregular problems and algorithms, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Internat. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 1\u201325.","DOI":"10.1007\/3-540-60321-2_1"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB42","doi-asserted-by":"crossref","unstructured":"J.R.W. Glauert, J.R. Kennaway, M.R. Sleep, Dactl: an experimental graph rewriting language, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 378\u2013395.","DOI":"10.1007\/BFb0017401"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB43","doi-asserted-by":"crossref","unstructured":"P.W. Grant, M.F. Webster, X. Zhang, Solving computational fluid dynamics problems on unstructured grids with distributed parallel processing, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Internat. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 187\u2013197.","DOI":"10.1007\/3-540-60321-2_16"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB44","doi-asserted-by":"crossref","unstructured":"R. Gupta, SPMD execution of programs with dynamic data structures on distributed memory machines Proc. Internat. Conf. on Computer Languages, Oakland, California, 20\u201323 April, IEEE Computer Society Press, 1992, pp. 232\u2013241.","DOI":"10.1109\/ICCL.1992.185487"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB45","doi-asserted-by":"crossref","unstructured":"A. Habel, H.J. Kreowski, May we introduce to you: hyperedge replacement, in: H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld (Eds.), Proc. 3rd Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, Warrenton, Virginia, 2\u20136 December, Springer, Berlin, 1986, pp. 15\u201326.","DOI":"10.1007\/3-540-18771-5_41"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB46","doi-asserted-by":"crossref","unstructured":"B. Hendrickson, R. Leland, Multidimensional spectral load balancing, Technical Report SAND93-0074, Sandia National Laboratory, January 1993.","DOI":"10.2172\/6691328"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB47","doi-asserted-by":"crossref","unstructured":"B. Hoffmann, Modelling compiler generation by graph grammars, in: H. Ehrig, M. Magl, G. Rozenberg (Eds.), Proc. 2nd International Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, Haus Ohrbeck, West Germany, October 4\u20138, Springer, Berlin, 1982, 159\u2013171.","DOI":"10.1007\/BFb0000105"},{"issue":"3","key":"10.1016\/S0304-3975(98)00226-6_BIB48","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/151640.151644","article-title":"Abstract description of pointer data structures: An approach for improving the analysis and optimization of imperative programs","volume":"1","author":"Hummel","year":"1992","journal-title":"ACM Lett. Programm. Languages Systems"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB49","doi-asserted-by":"crossref","unstructured":"M. Jackel, ADA concurrency specified by graph grammars, in: G. Tinhofer, G. Schmidt, (Eds.), Proc. 12th International Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201986), Lecture Notes in Computer Science, vol. 246, Bernried, West Germany, 17\u201319 June, Springer, Berlin, 1986, pp. 41\u201357.","DOI":"10.1007\/3-540-17218-1_48"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB50","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0255(80)90038-9","article-title":"On the structure of node-label-controlled graph languages","volume":"20","author":"Janssens","year":"1980","journal-title":"Inform. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB51","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0020-0255(80)90039-0","article-title":"Restrictions, extensions and variations of NLC grammars","volume":"20","author":"Janssens","year":"1980","journal-title":"Inform. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB52","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF00289591","article-title":"A characterization of context-free string languages by directed nodel-label controlled graph grammars","volume":"16","author":"Janssens","year":"1981","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB53","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(82)90088-3","article-title":"Graph grammars with neighbourhood controlled embedding","volume":"21","author":"Janssens","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB54","doi-asserted-by":"crossref","unstructured":"D. Janssens, G. Rozenberg, Graph grammars with node-label controlled rewriting and embedding, in: H. Ehrig, M. Magl, G. Rozenberg (Eds.), Proc. 2nd Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, Haus Ohrbeck, West Germany, 4\u20138 October, Springer, Berlin, 1982, pp. 186\u2013203.","DOI":"10.1007\/BFb0000107"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB55","doi-asserted-by":"crossref","unstructured":"D. Janssens, G. Rozenberg, Hypergraph systems generating graph languages, in: H. Ehrig, M. Nagl, G. Rozenberg (Eds.), Proc. 2nd Internat. Workshop on Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, October, Springer, Berlin, 1983, pp. 172\u2013185.","DOI":"10.1007\/BFb0000106"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB56","doi-asserted-by":"crossref","unstructured":"D. Janssens, G. Rozenberg, Structured transformations and computation graphs for actor grammars, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, 446\u2013460.","DOI":"10.1007\/BFb0017405"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB57","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0146-664X(82)90036-3","article-title":"On sequential and parallel node-rewriting graph grammars","volume":"18","author":"Janssens","year":"1982","journal-title":"Comput. Graphics Image Process."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB58","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0734-189X(83)90028-2","article-title":"On sequential and parallel node-rewriting graph grammars, II","volume":"23","author":"Janssens","year":"1983","journal-title":"Comput. Vision Graphics Image Process."},{"issue":"6","key":"10.1016\/S0304-3975(98)00226-6_BIB59","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","article-title":"Optimization by simulated annealing: an experimental evaluation; Part 1: graph partitioning","volume":"37","author":"Johnson","year":"1989","journal-title":"Oper. Res."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB60","doi-asserted-by":"crossref","unstructured":"G. Karypis, V. Kumar, Multilevel k-way partitioning scheme for irregular graphs, Technical Report 96-064, University of Minnesota, Department of Computer Science, Minneapolis, MN, 55455, August 1995.","DOI":"10.1145\/369028.369103"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB61","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0304-3975(87)90079-X","article-title":"On \u201cOn graph rewritings\u201d","volume":"52","author":"Kennaway","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB62","doi-asserted-by":"crossref","unstructured":"B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Tech. J. (1970) 291\u2013307.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB63","doi-asserted-by":"crossref","unstructured":"N. Klarlund, M.I. Schwartzbach, Graph types, Conf. Record of the 20th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, Charleston, South Carolina, 10\u201313 January, 1993, pp. 196\u2013205.","DOI":"10.1145\/158511.158628"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB64","doi-asserted-by":"crossref","unstructured":"T. Kloks, Treewidth: Computations and Approximations, Lecture Notes in Computer Science, vol. 842, Springer, Berlin, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB65","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0255(90)90042-9","article-title":"On structured graph grammars I","volume":"52","author":"G. Rozenberg","year":"1990","journal-title":"Inform. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB66","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0255(90)90044-B","article-title":"On structured graph grammars II","volume":"52","author":"Kreowski","year":"1990","journal-title":"Inform. Sci."},{"issue":"1","key":"10.1016\/S0304-3975(98)00226-6_BIB67","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0206012","article-title":"A linear tree partitioning algorithm","volume":"6","author":"Kundu","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB68","doi-asserted-by":"crossref","unstructured":"C. Lautemann, Decomposition trees: structured graph representation and efficient algorithms, in: M. Dauchet, N. Nivat (Eds.), Proc. 13th Colloq. on Trees in Algebra and Programming, Lecture Notes in Computer Science, vol. 299, Springer, Berlin, March 1988, pp. 28\u201339.","DOI":"10.1007\/BFb0026094"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB69","doi-asserted-by":"crossref","unstructured":"C. Lautemann, Efficient algorithms on context-free graph languages, in: T. Lepist\u00f6, A. Salomaa (Eds.), Proc. 15th Internat. Colloquium On Automata, Languages and Programming, Lecture Notes in Computer Science, vo. 317, Tampere, Finland, 11\u201315 July, Springer, Berlin, 1998, 362\u2013378.","DOI":"10.1007\/3-540-19488-6_128"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB70","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF00289017","article-title":"The complexity of graph languages generated by hyperedge replacement","volume":"27","author":"Lautemann","year":"1990","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB71","doi-asserted-by":"crossref","unstructured":"C. Lautemann, Tree automata, tree decomposition and hyperedge replacement, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th International Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 520\u2013537.","DOI":"10.1007\/BFb0017410"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB72","doi-asserted-by":"crossref","unstructured":"T. Lepist\u00f6, A. Salomaa (Eds.) Proc. 15th Internat. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Tampere, Finland, 11\u201315 July, Springer, Berlin, 1988.","DOI":"10.1007\/3-540-19488-6"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB73","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0022-5193(68)90079-9","article-title":"Mathematical models for cellular interaction in development","volume":"18","author":"Lindenmayer","year":"1968","journal-title":"J. Theoret. Biol."},{"issue":"1","key":"10.1016\/S0304-3975(98)00226-6_BIB74","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","article-title":"Locality in distributed graph algorithms","volume":"21","author":"Linial","year":"1992","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0304-3975(98)00226-6_BIB75","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB76","unstructured":"I. Litovsky, Y. M\u00e9tivier, W. Zielonka, The power and the limitations of local computations on graphs, in: E.W. Mayr (Eds.), Proc. 18th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201992), Lecture Notes in Computer Science, vol. 657, Wiesbaden-Naurod, Germany, 18\u201320 June, Springer, Berlin, 1992, pp. 333\u2013345."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB77","doi-asserted-by":"crossref","unstructured":"M. L\u00f6we, H. Ehrig, Algebraic approach to graph transformation based on single pushout derivations, in: R.H. Mohring (Eds.), Proc. 16th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201990), Lecture Notes in Computer Science, vol. 484, June 1991, Springer, Berlin, pp. 338\u2013353.","DOI":"10.1007\/3-540-53832-1_52"},{"issue":"3","key":"10.1016\/S0304-3975(98)00226-6_BIB78","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1147\/rd.183.0217","article-title":"Efficient algorithm for the partitioning of trees","volume":"18","author":"Lukes","year":"1974","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB79","doi-asserted-by":"crossref","unstructured":"S. Miguet, J.-M. Pierson, Load balancing strategies for a parallel system of particles, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Int. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 255\u2013260.","DOI":"10.1007\/3-540-60321-2_21"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB80","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0019-9958(70)90135-X","article-title":"Separable graphs, planar graphs and web grammars","volume":"16","author":"Montanari","year":"1970","journal-title":"Inform. Control"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB81","doi-asserted-by":"crossref","unstructured":"M. Nagl, G. Engels, R. Gall, W. Sch\u00e4fer, Software specification by graph grammars, in: H. Ehrig, Manfred Magl, G. Rozenberg (Eds.), Proc. 2nd Internat, Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 153, Haus Ohrbeck, West Germany, 4\u20138 October, Springer, Berlin, 1982, pp. 267\u2013287.","DOI":"10.1007\/BFb0000113"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB82","doi-asserted-by":"crossref","unstructured":"M. Nagl, On the relation between graph grammars and graph l-systems, in: M. Karpinski (Ed.), Fundamentals of Computation Theory: Proc. Internat. FCT-Conf., Lecture Notes in Computer Science, vol. 56, Poznan-Kornik, Poland, September, Springer, Berlin, 1977, pp. 142\u2013151.","DOI":"10.1007\/3-540-08442-8_80"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB83","doi-asserted-by":"crossref","unstructured":"T. Nakanishi, K. Joe, H. Saito, C.D. Polychronopoulos, A. Fukuda, K. Araki, The data partitioning graph: extending data and control dependencies for data partitioning, in: K. Pingali, U. Banerjee, D. Gelernter, A. Nicolau, D. Padua (Eds.), Proc. 7th Internat. Workshop on Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, vol. 892, Ithaca, New York, 8\u201310 August, 1994, Springer, Berlin, pp. 170\u2013185.","DOI":"10.1007\/BFb0025878"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB84","doi-asserted-by":"crossref","unstructured":"ESPRIT Basic Research Working Group No.3299, Computing by graph transformation: overall aims and new results, in H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 688\u2013703.","DOI":"10.1007\/BFb0017422"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB85","unstructured":"Y. Okada, M. Hayashi, Graph rewriting systems and their application to network reliability analysis, in: G. Schmidt, R. Berghammer (Eds.), Proc. 17th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201991), Lecture Notes in Computer Science, vol. 570, Fischbachau, Germany, 17\u201319 June, Springer, Berlin, 1991, pp. 36\u201347."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB86","series-title":"Lindenmayer Systems","first-page":"193","article-title":"L-systems: from formalism to programming languages","author":"Prusinkiewicz","year":"1992"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB87","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(84)90021-5","article-title":"On graph rewritings","volume":"32","author":"Raoult","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB88","doi-asserted-by":"crossref","unstructured":"R. Reischuk, Graph theoretical methods for the design of parallel algorithms, in: L. Budach, (Ed.), Proc. 8th Internat. Conference on Fundamentals of Computation Theory (FCT \u201991), Lecture Notes in Computer Science, vol. 529, Gosen, Germany, September, Springer, Berlin, 1991, 61\u201367.","DOI":"10.1007\/3-540-54458-5_50"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB89","unstructured":"J. Rekers, On the use of graph grammars for defining the syntax of graphical languages, Technical Report 94-11, Department of Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands, 1994. Available by ftp: ftp.wi.leidenuniv.nl as pub\/cs-techreports\/tr94-11.ps.gz."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB90","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors II: algorithmic aspects of treewidth","volume":"7","author":"Robertson","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB91","doi-asserted-by":"crossref","unstructured":"P. Sanders, Better algorithms for parallel backtracking, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Int. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 333\u2013347.","DOI":"10.1007\/3-540-60321-2_27"},{"issue":"1","key":"10.1016\/S0304-3975(98)00226-6_BIB92","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","article-title":"Finding k cuts within twice the optimal","volume":"24","author":"Saran","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB93","doi-asserted-by":"crossref","unstructured":"H.J. Schneider, H. Ehrig (Eds.), Graph Transformations in Computer Science: Proc. Internat. Workshop, Lecture Notes in Computer Science, vol. 776, Dagstuhl Castle, Germany, January 1993, Springer, Berlin.","DOI":"10.1007\/3-540-57787-4"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB94","doi-asserted-by":"crossref","unstructured":"A. Sch\u00fcrr, Introduction to PROGRESS, an attribute graph grammar based specification language, in: M. Nagl, (Ed.), Proc. 15th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201989), Lecture Notes in Computer Science, vol. 441, Castle Rolduc, The Netherlands, June, Springer, Berlin, 1989, 151\u2013165.","DOI":"10.1007\/3-540-52292-1_11"},{"key":"10.1016\/S0304-3975(98)00226-6_BIB95","doi-asserted-by":"crossref","unstructured":"A. Sch\u00fcrr, PROGRESS: A VHL-language based on graph grammars, in: H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.), Proc. 4th Internat. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532, Bremen, Germany, 5\u20139 March, Springer, Berlin, 1990, pp. 641\u2013659.","DOI":"10.1007\/BFb0017419"},{"issue":"2","key":"10.1016\/S0304-3975(98)00226-6_BIB96","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0020-0190(82)90086-2","article-title":"Context-free grammars as a tool for describing polynomial-time subclasses of hard problems","volume":"14","author":"Slisenko","year":"1982","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"10.1016\/S0304-3975(98)00226-6_BIB97","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/0304-3975(93)90031-N","article-title":"Edge separators for graphs of bounded genus with applications","volume":"112","author":"S\u00fdkora","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00226-6_BIB98","doi-asserted-by":"crossref","unstructured":"C. Walshaw, M. Cross, M.G. Everett, S. Johnson, K. McManus, Partitioning & mapping of unstructured meshes to parallel machine topologies, in: A. Ferreira, J. Rolim (Eds.), Parallel Algorithms for Irregularly Structured Problems: Proc. 2nd Internat. Workshop, IRREGULAR \u201995, Lecture Notes in Computer Science, vol. 980, Lyon, France, 4\u20136 September, Springer, Berlin, 1995, pp. 121\u2013126.","DOI":"10.1007\/3-540-60321-2_10"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598002266?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598002266?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T16:12:20Z","timestamp":1733501540000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397598002266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,5]]},"references-count":98,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,5]]}},"alternative-id":["S0304397598002266"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(98)00226-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2000,5]]}}}