{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T13:13:56Z","timestamp":1718111636554},"reference-count":141,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2009,1,15]]},"abstract":"\n Fast algorithms can be created for many graph problems when instances are confined to classes of graphs that are recursively constructed. This article first describes some basic conceptual notions regarding the design of such fast algorithms, and then the coverage proceeds through several recursive graph classes. Specific classes include trees, series-parallel graphs,\n k<\/jats:italic>\n -terminal graphs, treewidth-\n k<\/jats:italic>\n graphs,\n k<\/jats:italic>\n -trees, partial\n k<\/jats:italic>\n -trees,\n k<\/jats:italic>\n -jackknife graphs, pathwidth-\n k<\/jats:italic>\n graphs, bandwidth-\n k<\/jats:italic>\n graphs, cutwidth-\n k<\/jats:italic>\n graphs, branchwidth-\n k<\/jats:italic>\n graphs, Halin graphs, cographs, cliquewidth-\n k<\/jats:italic>\n graphs,\n k<\/jats:italic>\n -NLC graphs,\n k<\/jats:italic>\n -HB graphs, and rankwidth-\n k<\/jats:italic>\n graphs. The definition of each class is provided. Typical algorithms are applied to solve problems on instances of most classes. Relationships between the classes are also discussed.\n <\/jats:p>","DOI":"10.1145\/1456650.1456654","type":"journal-article","created":{"date-parts":[[2009,1,13]],"date-time":"2009-01-13T13:15:48Z","timestamp":1231852548000},"page":"1-51","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Solving problems on recursively constructed graphs"],"prefix":"10.1145","volume":"41","author":[{"given":"Richard B.","family":"Borie","sequence":"first","affiliation":[{"name":"University of Alabama, Tuscaloosa, AL"}]},{"given":"R. Gary","family":"Parker","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}]},{"given":"Craig A.","family":"Tovey","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}]}],"member":"320","published-online":{"date-parts":[[2009,1,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 7--15","author":"Amir E.","year":"2001","unstructured":"Amir , E. 2001 . Efficient approximation for triangulation of minimum treewidth . In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 7--15 . Amir, E. 2001. Efficient approximation for triangulation of minimum treewidth. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 7--15."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3765.3773"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169807"},{"key":"e_1_2_1_5_1","first-page":"2","article-title":"Efficient algorithms and partial k-trees","volume":"54","author":"Arnborg S.","year":"1994","unstructured":"Arnborg , S. , Hedetniemi , S. , and Proskurowski , A. 1994 . Efficient algorithms and partial k-trees . Discrete Appl. Math. 54 , 2 -- 3 . Guest editors of special issue. Arnborg, S., Hedetniemi, S., and Proskurowski, A. 1994. Efficient algorithms and partial k-trees. Discrete Appl. Math. 54, 2--3. Guest editors of special issue.","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_7_1","first-page":"69","article-title":"Characterization and recognition of partial k-trees","volume":"47","author":"Arnborg S.","year":"1985","unstructured":"Arnborg , S. and Proskurowski , A. 1985 . Characterization and recognition of partial k-trees . Congressus Numer. 47 , 69 -- 75 . Arnborg, S. and Proskurowski, A. 1985. Characterization and recognition of partial k-trees. Congressus Numer. 47, 69--75.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607033"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90292-P"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)90120-7"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science","volume":"4041","author":"Bachoore E.","unstructured":"Bachoore , E. and Bodlaender , H . 2006. A branch-and-bound algorithm for exact, upper, and lower bounds on treewidth . In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science , vol. 4041 . Springer, 255--266. Bachoore, E. and Bodlaender, H. 2006. A branch-and-bound algorithm for exact, upper, and lower bounds on treewidth. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol. 4041. Springer, 255--266."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00075-8"},{"key":"e_1_2_1_14_1","first-page":"141","article-title":"Properties and characterizations of k-trees","volume":"18","author":"Beineke L.","year":"1971","unstructured":"Beineke , L. and Pippert , R. 1971 . Properties and characterizations of k-trees . Math. 18 , 141 -- 151 . Beineke, L. and Pippert, R. 1971. Properties and characterizations of k-trees. Math. 18, 141--151.","journal-title":"Math."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90068-U"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00126-7"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 15th International Colloquium on Automata, Languages and Programming","author":"Bodlaender H.","unstructured":"Bodlaender , H. 1988. Dynamic programming algorithms on graphs with bounded tree-width . In Proceedings of the 15th International Colloquium on Automata, Languages and Programming . Lecture Notes in Computer Science , vol. 317 . Springer , 105--109. Bodlaender, H. 1988. Dynamic programming algorithms on graphs with bounded tree-width. In Proceedings of the 15th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 317. Springer, 105--109."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender H.","year":"1993","unstructured":"Bodlaender , H. 1993 . A tourist guide through treewidth . Acta Cybernetica 11 , 1 -- 23 . Bodlaender, H. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1--23.","journal-title":"Acta Cybernetica"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_60"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 574--583","author":"Bodlaender H.","unstructured":"Bodlaender , H. , Gustedt , J. , and Telle , J . 1998. Linear-Time register allocation for a fixed number of registers and no stack variables . In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 574--583 . Bodlaender, H., Gustedt, J., and Telle, J. 1998. Linear-Time register allocation for a fixed number of registers and no stack variables. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 574--583."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.2005.00274.x"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00117"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406014"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01293664"},{"key":"e_1_2_1_34_1","unstructured":"Borie R. Johnson J. Raghavan V. and Spinrad J. 2002. Robust polynomial time algorithms on cliquewidth-k graphs. Manuscript. Borie R. Johnson J. Raghavan V. and Spinrad J. 2002. Robust polynomial time algorithms on cliquewidth-k graphs. Manuscript."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02115752"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404043"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"issue":"4","key":"e_1_2_1_38_1","first-page":"1046","article-title":"Algorithms on recursively constructed graphs. In Handbook of Graph Theory, J. Gross and J. Yellen, eds. CRC Press","volume":"10","author":"Borie R.","year":"2004","unstructured":"Borie , R. , Parker , R. , and Tovey , C. 2004 . Algorithms on recursively constructed graphs. In Handbook of Graph Theory, J. Gross and J. Yellen, eds. CRC Press , Chapter 10 . 4 , 1046 -- 1066 . Borie, R., Parker, R., and Tovey, C. 2004. Algorithms on recursively constructed graphs. In Handbook of Graph Theory, J. Gross and J. Yellen, eds. CRC Press, Chapter 10.4, 1046--1066.","journal-title":"Chapter"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00440-2"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/302970"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science","volume":"2647","author":"Clautiaux F.","unstructured":"Clautiaux , F. , Carlier , J. , Moukrim , A. , and Negre , S . 2003. New lower and upper bounds for graph treewidth . In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science , vol. 2647 . Springer, 70--80. Clautiaux, F., Carlier, J., Moukrim, A., and Negre, S. 2003. New lower and upper bounds for graph treewidth. In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science, vol. 2647. Springer, 70--80."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro:2004011"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science","volume":"1776","author":"Corneil D.","unstructured":"Corneil , D. , Habib , M. , Lanlignel , J. , Reed , B. , and Rotics , U . 2000. Polynomial-Time recognition of clique-width \u2264 3 graphs . In Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science , vol. 1776 . Springer, 126--134. Corneil, D., Habib, M., Lanlignel, J., Reed, B., and Rotics, U. 2000. Polynomial-Time recognition of clique-width \u2264 3 graphs. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 1776. Springer, 126--134."},{"key":"e_1_2_1_44_1","first-page":"237","article-title":"Families of recursively defined perfect graphs","volume":"39","author":"Corneil D.","year":"1983","unstructured":"Corneil , D. and Kirkpatrick , D. 1983 . Families of recursively defined perfect graphs . Congressus Numer. 39 , 237 -- 246 . Corneil, D. and Kirkpatrick, D. 1983. Families of recursively defined perfect graphs. Congressus Numer. 39, 237--246.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"e_1_2_1_46_1","first-page":"249","article-title":"Cographs: Recognition, applications and algorithms","volume":"43","author":"Corneil D.","year":"1984","unstructured":"Corneil , D. , Perl , Y. , and Stewart , L. 1984 . Cographs: Recognition, applications and algorithms . Congressus Numer. 43 , 249 -- 258 . Corneil, D., Perl, Y., and Stewart, L. 1984. Cographs: Recognition, applications and algorithms. Congressus Numer. 43, 249--258.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701385351"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591867"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1992260302571"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)94698-V"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00083-6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00221-3"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_63_1","first-page":"16","article-title":"On combinatorial properties of matrices","volume":"38","author":"Egervary E.","year":"1931","unstructured":"Egervary , E. 1931 . On combinatorial properties of matrices . Math. Phys. Pages 38 , 16 -- 28 . Egervary, E. 1931. On combinatorial properties of matrices. Math. Phys. Pages 38, 16--28.","journal-title":"Math. Phys. Pages"},{"key":"e_1_2_1_64_1","first-page":"105","article-title":"Partial k-tree algorithms","volume":"64","author":"El-Mallah E.","year":"1988","unstructured":"El-Mallah , E. and Colbourn , C. 1988 . Partial k-tree algorithms . Congressus Numer. 64 , 105 -- 119 . El-Mallah, E. and Colbourn, C. 1988. Partial k-tree algorithms. Congressus Numer. 64, 105--119.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 27th International Workshop on Graph Theory. Lecture Notes in Computer Science","volume":"2204","author":"Espelage W.","unstructured":"Espelage , W. , Gurski , F. , and Wanke , E . 2001. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time . In Proceedings of the 27th International Workshop on Graph Theory. Lecture Notes in Computer Science , vol. 2204 . Springer, 117--128. Espelage, W., Gurski, F., and Wanke, E. 2001. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In Proceedings of the 27th International Workshop on Graph Theory. Lecture Notes in Computer Science, vol. 2204. Springer, 117--128."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060674"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence, 201--208","author":"Gogate V.","unstructured":"Gogate , V. and Dechter , R . 2004. A complete anytime algorithm for treewidth . In Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence, 201--208 . Gogate, V. and Dechter, R. 2004. A complete anytime algorithm for treewidth. In Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence, 201--208."},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the 25th International Workshop on Graph Theory. Lecture Notes in Computer Science","volume":"1665","author":"Golumbic M.","unstructured":"Golumbic , M. and Rotics , U . 1999. On the clique-width of perfect graph classes . In Proceedings of the 25th International Workshop on Graph Theory. Lecture Notes in Computer Science , vol. 1665 . Springer, 135--147. Golumbic, M. and Rotics, U. 1999. On the clique-width of perfect graph classes. In Proceedings of the 25th International Workshop on Graph Theory. Lecture Notes in Computer Science, vol. 1665. Springer, 135--147."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404031"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of the 26th International Workshop on Graph Theory. Lecture Notes in Computer Science","volume":"1928","author":"Gurski F.","unstructured":"Gurski , F. and Wanke , E . 2000. The tree-width of clique-width bounded graphs without Kn,n . In Proceedings of the 26th International Workshop on Graph Theory. Lecture Notes in Computer Science , vol. 1928 . Springer, 196--205. Gurski, F. and Wanke, E. 2000. The tree-width of clique-width bounded graphs without Kn,n. In Proceedings of the 26th International Workshop on Graph Theory. Lecture Notes in Computer Science, vol. 1928. Springer, 196--205."},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of the 6th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science","volume":"2976","author":"Gurski F.","unstructured":"Gurski , F. and Wanke , E . 2004. Vertex disjoint paths on clique-width bounded graphs . In Proceedings of the 6th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science , vol. 2976 . Springer, 119--128. Gurski, F. and Wanke, E. 2004. Vertex disjoint paths on clique-width bounded graphs. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 2976. Springer, 119--128."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.02.026"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-386870-1.50030-7"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90061-7"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","unstructured":"Hicks I. Koster A. and Koloto\u011flu E. 2005. Branch and tree decomposition techniques for discrete optimization. In TutORials 2005 J. Smith ed. Tutorials in Operations Research. INFORMS New Orleans LA 1--29. Hicks I. Koster A. and Koloto\u011flu E. 2005. Branch and tree decomposition techniques for discrete optimization. In TutORials 2005 J. Smith ed. Tutorials in Operations Research. INFORMS New Orleans LA 1--29.","DOI":"10.1287\/educ.1053.0017"},{"key":"e_1_2_1_78_1","first-page":"65","article-title":"On some results pertaining to Halin graphs","volume":"93","author":"Horton S.","year":"1992","unstructured":"Horton , S. , Parker , R. , and Borie , R. 1992 . On some results pertaining to Halin graphs . Congressus Numer. 93 , 65 -- 86 . Horton, S., Parker, R., and Borie, R. 1992. On some results pertaining to Halin graphs. Congressus Numer. 93, 65--86.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000137"},{"key":"e_1_2_1_80_1","article-title":"Algorithms for multicolorings of partial k-trees. IEICE","author":"Ito T.","year":"2003","unstructured":"Ito , T. , Nishizeki , T. , and Zhou , X. 2003 . Algorithms for multicolorings of partial k-trees. IEICE Trans. Inf. Syst. E86-D, 191--200. Ito, T., Nishizeki, T., and Zhou, X. 2003. Algorithms for multicolorings of partial k-trees. IEICE Trans. Inf. Syst. E86-D, 191--200.","journal-title":"Trans. Inf. Syst. E86-D, 191--200."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00012-3"},{"key":"e_1_2_1_82_1","first-page":"269","article-title":"Bayesian updating in recursive graphical models by local computation","volume":"4","author":"Jensen F.","year":"1990","unstructured":"Jensen , F. , Lauritzen , S. , and Olesen , K. 1990 . Bayesian updating in recursive graphical models by local computation . Computat. Statist. Q. 4 , 269 -- 282 . Jensen, F., Lauritzen, S., and Olesen, K. 1990. Bayesian updating in recursive graphical models by local computation. Computat. Statist. Q. 4, 269--282.","journal-title":"Computat. Statist. Q."},{"key":"e_1_2_1_83_1","volume-title":"Congressus Numer. 132","author":"Johansson O.","year":"1998","unstructured":"Johansson , O. 1998 . Clique-Decomposition, NLC-decomposition, and modular decomposition relationships and results for random graphs . Congressus Numer. 132 , 39--60. Johansson, O. 1998. Clique-Decomposition, NLC-decomposition, and modular decomposition relationships and results for random graphs. Congressus Numer. 132, 39--60."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000223"},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the International Symposium on Circuits and Systems. IEEE, 1179--1182","author":"Kajitani Y.","unstructured":"Kajitani , Y. , Ishizuka , A. , and Ueno , S . 1985. A characterization of the partial k-tree in terms of certain structures . In Proceedings of the International Symposium on Circuits and Systems. IEEE, 1179--1182 . Kajitani, Y., Ishizuka, A., and Ueno, S. 1985. A characterization of the partial k-tree in terms of certain structures. In Proceedings of the International Symposium on Circuits and Systems. IEEE, 1179--1182."},{"key":"e_1_2_1_87_1","volume-title":"Complexity of Computer Computations","author":"Karp R.","unstructured":"Karp , R. 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Plenum Press , New York , 85--103. Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York, 85--103."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00240-6"},{"key":"e_1_2_1_89_1","unstructured":"Kassios I. 2001. Translating Borie-Parker-Tovey calculus into mutumorphisms. Manuscript. Kassios I. 2001. Translating Borie-Parker-Tovey calculus into mutumorphisms. Manuscript."},{"key":"e_1_2_1_90_1","volume-title":"Computer Science Logic","author":"Klarlund N.","year":"1997","unstructured":"Klarlund , N. 1998. Mona and Fido: The logic-automaton connection in practice . In Computer Science Logic 1997 . Lecture Notes in Computer Science, vol. 1414 . Springer , 311--326. Klarlund, N. 1998. Mona and Fido: The logic-automaton connection in practice. In Computer Science Logic 1997. Lecture Notes in Computer Science, vol. 1414. Springer, 311--326."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200128X"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1037"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00198-1"},{"key":"e_1_2_1_96_1","first-page":"157","article-title":"Local computations with probabilities on graphical structures and their application to expert systems","volume":"50","author":"Lauritzen S.","year":"1988","unstructured":"Lauritzen , S. and Spiegelhalter , D. 1988 . Local computations with probabilities on graphical structures and their application to expert systems . J. Royal Statist. Soc. Series B 50 , 157 -- 224 . Lauritzen, S. and Spiegelhalter, D. 1988. Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statist. Soc. Series B 50, 157--224.","journal-title":"J. Royal Statist. Soc. Series B"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101397773"},{"key":"e_1_2_1_98_1","volume-title":"Proceedings of the 32nd International Workshop on Graph Theory. Lecture Notes in Computer Science","volume":"4271","author":"Makowsky J.","unstructured":"Makowsky , J. , Rotics , U. , Averbouch , I. , and Godlin , B . 2006. Computing graph polynomials on graphs of bounded clique-width . In Proceedings of the 32nd International Workshop on Graph Theory. Lecture Notes in Computer Science , vol. 4271 . Springer, 191--204. Makowsky, J., Rotics, U., Averbouch, I., and Godlin, B. 2006. Computing graph polynomials on graphs of bounded clique-width. In Proceedings of the 32nd International Workshop on Graph Theory. Lecture Notes in Computer Science, vol. 4271. Springer, 191--204."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90020-Y"},{"key":"e_1_2_1_100_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 31st International Workshop on Graph Theory","author":"Oum S.","unstructured":"Oum , S. 2005a. Approximating rank-width and clique-width quickly . In Proceedings of the 31st International Workshop on Graph Theory . Lecture Notes in Computer Science , vol. 3787 . Springer , 49--58. Oum, S. 2005a. Approximating rank-width and clique-width quickly. In Proceedings of the 31st International Workshop on Graph Theory. Lecture Notes in Computer Science, vol. 3787. Springer, 49--58."},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/147\/01201"},{"key":"e_1_2_1_104_1","unstructured":"Rardin R. and Parker R. 1986. Subgraph isomorphism on partial 2-trees. Tech. Rep. Georgia Institute of Technology. Rardin R. and Parker R. 1986. Subgraph isomorphism on partial 2-trees. Tech. Rep. Georgia Institute of Technology."},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129734"},{"key":"e_1_2_1_106_1","volume-title":"Surveys in Combinatorics. London Mathematical Society Lecture Note Series","volume":"241","author":"Reed B.","year":"1997","unstructured":"Reed , B. 1997 . Treewidth and tangles: A new connectivity measure and some applications . In Surveys in Combinatorics. London Mathematical Society Lecture Note Series , vol. 241 . Cambridge University Press, London, 87--162. Invited papers from 16th British Combinatorial Conference. Reed, B. 1997. Treewidth and tangles: A new connectivity measure and some applications. In Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 241. Cambridge University Press, London, 87--162. Invited papers from 16th British Combinatorial Conference."},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90070-6"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90120-O"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90063-6"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90121-F"},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_2_1_118_1","volume-title":"XXII: Irrelevant vertices in linkage problems. Manuscript.","author":"Robertson N.","year":"1992","unstructured":"Robertson , N. and Seymour , P . 1992 . Graph minors XXII: Irrelevant vertices in linkage problems. Manuscript. Robertson, N. and Seymour, P. 1992. Graph minors XXII: Irrelevant vertices in linkage problems. Manuscript."},{"key":"e_1_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1007"},{"key":"e_1_2_1_120_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_121_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_1_122_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_2_1_124_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90042-9"},{"key":"e_1_2_1_126_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193243043"},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1145\/357766.351254"},{"key":"e_1_2_1_128_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200304"},{"key":"e_1_2_1_129_1","volume-title":"Linear-Time algorithms for NP-complete problems restricted to partial k-trees","author":"Scheffler P.","unstructured":"Scheffler , P. 1987. Linear-Time algorithms for NP-complete problems restricted to partial k-trees . Tech. Rep. R-MATH-03\/87, Akademie der Wissenschaften der DDR. Scheffler, P. 1987. Linear-Time algorithms for NP-complete problems restricted to partial k-trees. Tech. Rep. R-MATH-03\/87, Akademie der Wissenschaften der DDR."},{"key":"e_1_2_1_130_1","volume-title":"What graphs have bounded treewidth&quest","author":"Scheffler P.","unstructured":"Scheffler , P. 1988. What graphs have bounded treewidth&quest ; In Fischland Colloquium on Discrete Mathematics and Applications . Scheffler, P. 1988. What graphs have bounded treewidth? In Fischland Colloquium on Discrete Mathematics and Applications."},{"key":"e_1_2_1_132_1","unstructured":"Scheffler P. and Seese D. 1986. Graphs of bounded tree-width and linear-time algorithms for NP-complete problems. In Bilateral Seminar. Scheffler P. and Seese D. 1986. Graphs of bounded tree-width and linear-time algorithms for NP-complete problems. In Bilateral Seminar."},{"key":"e_1_2_1_133_1","volume-title":"Proceedings of the European Conference on Computer Algebra. Lecture Notes in Computer Science","volume":"378","author":"Scheffler P.","unstructured":"Scheffler , P. and Seese , D . 1988. A combinatorial and logical approach to linear-time computability . In Proceedings of the European Conference on Computer Algebra. Lecture Notes in Computer Science , vol. 378 . Springer, 379--380. Scheffler, P. and Seese, D. 1988. A combinatorial and logical approach to linear-time computability. In Proceedings of the European Conference on Computer Algebra. Lecture Notes in Computer Science, vol. 378. Springer, 379--380."},{"key":"e_1_2_1_134_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_1_135_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"e_1_2_1_136_1","volume-title":"Fields Institute Monographs","author":"Spinrad J.","unstructured":"Spinrad , J. 2003. Efficient Graph Representations . Fields Institute Monographs . AMS , Brooklyn, NY . Spinrad, J. 2003. Efficient Graph Representations. Fields Institute Monographs. AMS, Brooklyn, NY."},{"key":"e_1_2_1_137_1","volume-title":"Proceedings of the 9th Workshop on Graph-Theoretic Concepts in Computer Science, 342--353","author":"Syslo M.","year":"1983","unstructured":"Syslo , M. 1983 . NP-Complete problems on some tree-structured graphs: A review . In Proceedings of the 9th Workshop on Graph-Theoretic Concepts in Computer Science, 342--353 . Syslo, M. 1983. NP-Complete problems on some tree-structured graphs: A review. In Proceedings of the 9th Workshop on Graph-Theoretic Concepts in Computer Science, 342--353."},{"key":"e_1_2_1_138_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322328"},{"key":"e_1_2_1_139_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90226-E"},{"key":"e_1_2_1_140_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"e_1_2_1_141_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_2_1_142_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"},{"key":"e_1_2_1_143_1","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing V.","year":"1964","unstructured":"Vizing , V. 1964 . On an estimate of the chromatic class of a p-graph . Discrete Anal. 3 , 25 -- 30 . Vizing, V. 1964. On an estimate of the chromatic class of a p-graph. Discrete Anal. 3, 25--30.","journal-title":"Discrete Anal."},{"key":"e_1_2_1_144_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90026-4"},{"key":"e_1_2_1_146_1","first-page":"161","article-title":"K-terminal recursive families of graphs","volume":"63","author":"Wimer T.","year":"1988","unstructured":"Wimer , T. and Hedetniemi , S. 1988 . K-terminal recursive families of graphs . Congressus Numer. 63 , 161 -- 176 . Wimer, T. and Hedetniemi, S. 1988. K-terminal recursive families of graphs. Congressus Numer. 63, 161--176.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_147_1","first-page":"43","article-title":"A methodology for constructing linear graph algorithms","volume":"50","author":"Wimer T.","year":"1985","unstructured":"Wimer , T. , Hedetniemi , S. , and Laskar , R. 1985 . A methodology for constructing linear graph algorithms . Congressus Numer. 50 , 43 -- 60 . Wimer, T., Hedetniemi, S., and Laskar, R. 1985. A methodology for constructing linear graph algorithms. Congressus Numer. 50, 43--60.","journal-title":"Congressus Numer."},{"key":"e_1_2_1_148_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010017"},{"key":"e_1_2_1_149_1","article-title":"Generalized vertex-colorings of partial k-trees. IEICE","author":"Zhou X.","year":"2000","unstructured":"Zhou , X. , Kanari , Y. , and Nishizeki , T. 2000 . Generalized vertex-colorings of partial k-trees. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E83-A, 671--678. Zhou, X., Kanari, Y., and Nishizeki, T. 2000. Generalized vertex-colorings of partial k-trees. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E83-A, 671--678.","journal-title":"Trans. Fundam. Electron. Commun. Comput. Sci. E83-A, 671--678."},{"key":"e_1_2_1_150_1","volume-title":"Proceedings of the 1st Annual European Symposium on Algorithms. Lecture Notes in Computer Science","volume":"726","author":"Zhou X.","unstructured":"Zhou , X. , Nakano , S. , and Nishizeki , T . 1993. A linear algorithm for edge-coloring partial k-trees . In Proceedings of the 1st Annual European Symposium on Algorithms. Lecture Notes in Computer Science , vol. 726 . Springer, 409--418. Zhou, X., Nakano, S., and Nishizeki, T. 1993. A linear algorithm for edge-coloring partial k-trees. In Proceedings of the 1st Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 726. Springer, 409--418."},{"key":"e_1_2_1_151_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0061"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1456650.1456654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T09:21:05Z","timestamp":1672305665000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1456650.1456654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,15]]},"references-count":141,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1,15]]}},"alternative-id":["10.1145\/1456650.1456654"],"URL":"https:\/\/doi.org\/10.1145\/1456650.1456654","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,15]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}