Solving problems on recursively constructed graphs

ABSTRACT

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, k-terminal graphs, treewidth-k graphs, k-trees, partial k-trees, k-jackknife graphs, pathwidth-k graphs, bandwidth-k graphs, cutwidth-k graphs, branchwidth-k graphs, Halin graphs, cographs, cliquewidth-k graphs, k-NLC graphs, k-HB graphs, and rankwidth-k 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.

REFERENCES

• 1: Eyal Amir, Efficient Approximation for Triangulation of Minimum Treewidth, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.7-15, August 02-05, 2001
• 2: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 3: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 4: Stefan Arnborg , Bruno Courcelle , Andrzej Proskurowski , Detlef Seese, An algebraic theory of graph reduction, Journal of the ACM (JACM), v.40 n.5, p.1134-1164, Nov. 1993 [doi>10.1145/174147.169807]
• 5: 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.
• 6: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 7: Arnborg, S. and Proskurowski, A. 1985. Characterization and recognition of partial k-trees. Congressus Numer. 47, 69--75.
• 8: Stefan Arnborg , Andrzej Proskurowski, Characterization and recognition of partial 3-trees, SIAM Journal on Algebraic and Discrete Methods, v.7 n.2, p.305-314, April 1986 [doi>10.1137/0607033]
• 9: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 10: S. Arnborg , A. Proskurowski , D. G. Corneil, Forbidden minors characterization of partial 3-trees, Discrete Mathematics, v.80 n.1, p.1-19, February 1990 [doi>10.1016/0012-365X(90)90292-P]
• 11: Luitpold Babel , Stephan Olariu, On the structure of graphs with few P4s, Discrete Applied Mathematics, v.84 n.1-3, p.1-13, May 15, 1998 [doi>10.1016/S0166-218X(97)90120-7]
• 12: 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.
• 13: Ann Becker , Dan Geiger, A sufficiently fast algorithm for finding close to optimal clique trees, Artificial Intelligence, v.125 n.1-2, p.3-17, Jan. 2001 [doi>10.1016/S0004-3702(00)00075-8]
• 14: Beineke, L. and Pippert, R. 1971. Properties and characterizations of k-trees. Math. 18, 141--151.
• 15: M. W. Bern , E. L. Lawler , A. L. Wong, Linear-time computation of optimal subgraphs of decomposable graphs, Journal of Algorithms, v.8 n.2, p.216-235, June 1987 [doi>10.1016/0196-6774(87)90039-3]
• 16: Dan Bienstock , Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a forest, Journal of Combinatorial Theory Series B, v.52 n.2, p.274-283, July 1991 [doi>10.1016/0095-8956(91)90068-U]
• 17: Jean R. S. Blair , Pinar Heggernes , Jean Arne Telle, A practical algorithm for making filled graphs minimal, Theoretical Computer Science, v.250 n.1-2, p.125-141, Jan 6, 2001 [doi>10.1016/S0304-3975(99)00126-7]
• 18: Bodlaender, H. 1987. Dynamic programming on graphs with bounded tree-width. Tech. Rep., Massachusetts Institute of Technology.
• 19: Hans L. Bodlaender, Dynamic Programming on Graphs with Bounded Treewidth, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.105-118, July 11-15, 1988
• 20: Hans L. Boblaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Journal of Algorithms, v.11 n.4, p.631-643, Dec. 1990 [doi>10.1016/0196-6774(90)90013-5]
• 21: Bodlaender, H. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1--23.
• 22: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 23: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4]
• 24: Hans L. Bodlaender , Fedor V. Fomin , Arie M. C. A. Koster , Dieter Kratsch , Dimitrios M. Thilikos, On exact algorithms for treewidth, Proceedings of the 14th conference on Annual European Symposium, p.672-683, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_60]
• 25: Hans L. Bodlaender , John R. Gilbert , Hjálmtýr Hafsteinsson , Ton Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, v.18 n.2, p.238-255, March 1995 [doi>10.1006/jagm.1995.1009]
• 26: Hans Bodlaender , Jens Gustedt , Jan Arne Telle, Linear-time register allocation for a fixed number of registers, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.574-583, January 25-27, 1998, San Francisco, California, United States
• 27: Hans L. Bodlaender , Ton Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, v.21 n.2, p.358-402, Sept. 1996 [doi>10.1006/jagm.1996.0049]
• 28: Bodlaender, H. and Koster, A. 2006. Safe separators for treewidth. Discrete Math. 306, 337--350.
• 29: Bodlaender, H., Koster, A., and van den Eijkhof, F. 2005. Pre-Processing rules for triangulation of probabilistic networks. Comput. Intell. 21, 286--305.
• 30: Bodlaender, H., Koster, A., and Wolle, T. 2006. Contraction and treewidth lower bounds. J. Graph Algor. Appl. 10, 5--49.
• 31: Hans L. Bodlaender , Rolf H. Möhring, The pathwidth and treewidth of cographs, SIAM Journal on Discrete Mathematics, v.6 n.2, p.181-188, May 1993 [doi>10.1137/0406014]
• 32: Richard Bryan Borie , R. Gary Parker , Craig A. Tovey, Recursively constructed graph families: membership and linear algorithms, Georgia Institute of Technology, Atlanta, GA, 1988
• 33: Borie, R. 1995. Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica 14, 123--137.
• 34: Borie, R., Johnson, J., Raghavan, V., and Spinrad, J. 2002. Robust polynomial time algorithms on cliquewidth-k graphs. Manuscript.
• 35: Borie, R., Parker, R., and Tovey, C. 1991a. Algorithms for recognition of regular properties and decomposition of recursive graph families. Annals Oper. Res. 33, 127--149.
• 36: Richard B. Borie , R. Gary Parker , Craig A. Tovey, Deterministic decomposition of recursive graph classes, SIAM Journal on Discrete Mathematics, v.4 n.4, p.481-501, Nov. 1991 [doi>10.1137/0404043]
• 37: Borie, R., Parker, R., and Tovey, C. 1992. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555--581.
• 38: 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.
• 39: V. Bouchitté , D. Kratsch , H. Müller , I. Todinca, On treewidth approximations, Discrete Applied Mathematics, v.136 n.2-3, p.183-196, 15 February 2004 [doi>10.1016/S0166-218X(03)00440-2]
• 40: Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 41: 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.
• 42: Clautiaux, F., Moukrim, A., Negre, S., and Carlier, J. 2004. Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Oper. Res. 38, 13--26.
• 43: Derek G. Corneil , Michel Habib , Jean-Marc Lanlignel , Bruce A. Reed , Udi Rotics, Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract), Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.126-134, April 10-14, 2000
• 44: Corneil, D. and Kirkpatrick, D. 1983. Families of recursively defined perfect graphs. Congressus Numer. 39, 237--246.
• 45: Corneil, D., Lerchs, H., and Burlington, L. 1981. Complement reducible graphs. Discrete Appl. Math. 3, 163--174.
• 46: Corneil, D., Perl, Y., and Stewart, L. 1984. Cographs: Recognition, applications and algorithms. Congressus Numer. 43, 249--258.
• 47: Corneil, D., Perl, Y., and Stewart, L. 1985. A linear recognition algorithm for cographs. SIAM Journal on Comput. 14, 926--934.
• 48: Derek G. Corneil , Udi Rotics, On the Relationship Between Clique-Width and Treewidth, SIAM Journal on Computing, v.34 n.4, p.825-847, 2005 [doi>10.1137/S0097539701385351]
• 49: Cornuejols, G., Naddef, D., and Pulleyblank, W. 1983. Halin graphs and the travelling salesman problem. Math. Program. 26, 287--294.
• 50: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• 51: Courcelle, B. 1992. The monadic second-order logic of graphs III: Tree-Decompositions, minors, and complexity issues. Theor. Inf. Appl. 26, 257--286.
• 52: Courcelle, B. 1995. The monadic second-order logic of graphs VIII: Orientations. Annals Pure Appl. Logic 72, 103--143.
• 53: Bruno Courcelle, The monadic second-order logic of graphs X: linear orderings, Theoretical Computer Science, v.160 n.1-2, p.87-143, June 10, 1996 [doi>10.1016/0304-3975(95)00083-6]
• 54: Bruno Courcelle , Joost Engelfriet , Grzegorz Rozenberg, Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, v.46 n.2, p.218-270, April 1993 [doi>10.1016/0022-0000(93)90004-G]
• 55: Courcelle, B., Makowsky, J., and Rotics, U. 2000. Linear time solvable optimization problems on graphs of bounded clique width. Theory Comput. Syst. 33, 125--150.
• 56: B. Courcelle , J. A. Makowsky , U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Applied Mathematics, v.108 n.1, p.23-52, Feb. 15,2001 [doi>10.1016/S0166-218X(00)00221-3]
• 57: B. Courcelle , M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, v.109 n.1-2, p.49-82, March 1, 1993 [doi>10.1016/0304-3975(93)90064-Z]
• 58: Bruno Courcelle , Stephan Olariu, Upper bounds to the clique width of graphs, Discrete Applied Mathematics, v.101 n.1-3, p.77-114, April 15, 2000 [doi>10.1016/S0166-218X(99)00184-5]
• 59: de Fluiter, B. 1997. Algorithms for graphs of small treewidth. Ph.D. thesis, University of Utrecht.
• 60: Duffin, R. 1965. Topology of series-parallel networks. J. Math. Anal. Appl. 10, 303--318.
• 61: Edmonds, J. 1965a. Maximum matching and polyhedron of 0,1 vertices. J. Res. National Bureau Standards 69B, 125--130.
• 62: Edmonds, J. 1965b. Paths, trees, and flowers. Canadian J. Math. 17, 449--467.
• 63: Egervary, E. 1931. On combinatorial properties of matrices. Math. Phys. Pages 38, 16--28.
• 64: El-Mallah, E. and Colbourn, C. 1988. Partial k-tree algorithms. Congressus Numer. 64, 105--119.
• 65: Wolfgang Espelage , Frank Gurski , Egon Wanke, How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time, Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, p.117-128, June 14-16, 2001
• 66: Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060674]
• 67: Garey, M., Graham, R., Johnson, D., and Knuth, D. 1978. Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34, 477--495.
• 68: Gavril, F. 1972. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, 180--187.
• 69: Vibhav Gogate , Rina Dechter, A complete anytime algorithm for treewidth, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.201-208, July 07-11, 2004, Banff, Canada
• 70: Martin Charles Golumbic , Udi Rotics, On the Clique-Width of Perfect Graph Classes, Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, p.135-147, June 17-19, 1999
• 71: Granot, D. and Skorin-Kapov, D. 1991. NC algorithms for recognizing partial 2-trees and 3-trees. SIAM J. Algebr. Discrete Methods 4, 342--354.
• 72: Frank Gurski , Egon Wanke, The Tree-Width of Clique-Width Bounded Graphs Without Kn, n, Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, p.196-205, June 15-17, 2000
• 73: 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.
• 74: Frank Gurski , Egon Wanke, Vertex disjoint paths on clique-width bounded graphs, Theoretical Computer Science, v.359 n.1, p.188-199, 14 August 2006 [doi>10.1016/j.tcs.2006.02.026]
• 75: Hare, E., Hedetniemi, S., Laskar, R., Peters, K., and Wimer, T. 1987. Linear-time computability of combinatorial problems on generalized series-parallel graphs. Discrete Algor. Complexity 14, 437--457.
• 76: Xin He , Yaacov Yesha, Parallel recognition and decomposition of two terminal series parallel graphs, Information and Computation, v.75 n.1, p.15-38, October 1, 1987 [doi>10.1016/0890-5401(87)90061-7]
• 77: Hicks, I., Koster, A., and Kolotoğlu, 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.
• 78: Horton, S., Parker, R., and Borie, R. 1992. On some results pertaining to Halin graphs. Congressus Numer. 93, 65--86.
• 79: Isobe, S., Zhou, X., and Nishizeki, T. 1999. A polynomial-time algorithm for finding total colorings of partial k-trees. Int. J. Foundat. Comput. Sci. 10, 171--194.
• 80: Ito, T., Nishizeki, T., and Zhou, X. 2003. Algorithms for multicolorings of partial k-trees. IEICE Trans. Inf. Syst. E86-D, 191--200.
• 81: Beverly Jamison , Stephan Olariu, Linear time optimization for P 4-sparse graphs, Discrete Applied Mathematics, v.61 n.2, p.155-175, July 28, 1995 [doi>10.1016/0166-218X(94)00012-3]
• 82: Jensen, F., Lauritzen, S., and Olesen, K. 1990. Bayesian updating in recursive graphical models by local computation. Computat. Statist. Q. 4, 269--282.
• 83: Johansson, O. 1998. Clique-Decomposition, NLC-decomposition, and modular decomposition relationships and results for random graphs. Congressus Numer. 132, 39--60.
• 84: Johansson, O. 2000. NLC 2-decomposition in polynomial time. Int. J. Foundat. Comput. Sci. 11, 373--395.
• 85: Johnson, J. 2003. Polynomial time recognition and optimization algorithms on special classes of graphs. Ph.D. thesis, Vanderbilt University.
• 86: 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.
• 87: Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York, 85--103.
• 88: Md. Adul Kashem , Xiao Zhou , Takao Nishizeki, Algorithms for generalized vertex-rankings of partial k-trees, Theoretical Computer Science, v.240 n.2, p.407-427, June 17, 2000 [doi>10.1016/S0304-3975(99)00240-6]
• 89: Kassios, I. 2001. Translating Borie-Parker-Tovey calculus into mutumorphisms. Manuscript.
• 90: Nils Klarlund, Mona & Fido: The Logic-Automaton Connection in Practice, Selected Papers from the11th International Workshop on Computer Science Logic, p.311-326, August 23-29, 1997
• 91: Klarlund, N., Moller, A., and Schwartzbach, M. 2002. Mona implementation secrets. Int. J. Foundat. Comput. Sci. 13, 571--586.
• 92: Kloks, T. 1994. Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer.
• 93: T. Kloks , D. Kratsch, Treewidth of chordal bipartite graphs, Journal of Algorithms, v.19 n.2, p.266-281, Sept. 1995 [doi>10.1006/jagm.1995.1037]
• 94: Daniel Kobler , Udi Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Applied Mathematics, v.126 n.2-3, p.197-221, 15 March 2003 [doi>10.1016/S0166-218X(02)00198-1]
• 95: Koster, A. 1999. Frequency assignment—Models and algorithms. Ph.D. thesis, Maastricht University.
• 96: 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.
• 97: Brian Lucena, A New Lower Bound for Tree-Width Using Maximum Cardinality Search, SIAM Journal on Discrete Mathematics, v.16 n.3, p.345-353, 2003 [doi>10.1137/S0895480101397773]
• 98: 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.
• 99: Jiří Matoušek , Robin Thomas, Algorithms finding tree-decompositions of graphs, Journal of Algorithms, v.12 n.1, p.1-22, March 1991 [doi>10.1016/0196-6774(91)90020-Y]
• 100: 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.
• 101: Sang-Il Oum , Paul Seymour, Graphs of bounded rank-width, Princeton University, Princeton, NJ, 2005
• 102: Sang-il Oum , Paul Seymour, Approximating clique-width and branch-width, Journal of Combinatorial Theory Series B, v.96 n.4, p.514-528, July 2006 [doi>10.1016/j.jctb.2005.10.006]
• 103: Proskurowski, A. 1993. Graph reductions, and techniques for finding minimal forbidden minors. Graph Structure Theory 147, 591--600.
• 104: Rardin, R. and Parker, R. 1986. Subgraph isomorphism on partial 2-trees. Tech. Rep., Georgia Institute of Technology.
• 105: Bruce A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.221-228, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129734]
• 106: 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.
• 107: Michael Bruce Richey, Combinatorial optimization on series-parallel graphs: algorithms and complexity, Georgia Institute of Technology, Atlanta, GA, 1985
• 108: Robertson, N. and Seymour, P. 1983. Graph minors I: Excluding a forest. J. Combinatorial Theory Series B 35, 39--61.
• 109: Robertson, N. and Seymour, P. 1984. Graph minors III: Planar treewidth. J. Combinatorial Theory Series B 36, 49--64.
• 110: Robertson, N. and Seymour, P. 1986a. Graph minors II: Algorithmic aspects of treewidth. J. Algor. 7, 309--322.
• 111: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 112: Neil Robertson , P D Seymour, Graph minors. VI. Disjoint paths across a disc, Journal of Combinatorial Theory Series B, v.41 n.1, p.115-138, Aug. 1986 [doi>10.1016/0095-8956(86)90031-6]
• 113: Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
• 114: N. Robertson , P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory Series B, v.48 n.2, p.227-254, Apr. 1990 [doi>10.1016/0095-8956(90)90120-O]
• 115: P. D. Seymour, Graph minors. IX. Disjoint crossed paths, Journal of Combinatorial Theory Series B, v.49 n.1, p.40-77, Jun. 1990 [doi>10.1016/0095-8956(90)90063-6]
• 116: N. Robertson , P. D. Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, Journal of Combinatorial Theory Series B, v.48 n.2, p.255-288, Apr. 1990 [doi>10.1016/0095-8956(90)90121-F]
• 117: Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
• 118: Robertson, N. and Seymour, P. 1992. Graph minors XXII: Irrelevant vertices in linkage problems. Manuscript.
• 119: Neil Robertson , P. D. Seymour, Graph minors. XI.: circuits on a surface, Journal of Combinatorial Theory Series B, v.60 n.1, p.72-106, Jan. 1994 [doi>10.1006/jctb.1994.1007]
• 120: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 121: Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
• 122: Neil Robertson , P. D. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory Series B, v.92 n.2, p.325-357, November 2004 [doi>10.1016/j.jctb.2004.08.001]
• 123: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 124: Rose, D. 1974. On simple characterization of k-trees. Discrete Math. 7, 317--322.
• 125: Daniel Preston Sanders, Linear algorithms for graphs of tree-width at most four, Georgia Institute of Technology, Atlanta, GA, 1993
• 126: Daniel P. Sanders, On Linear Recognition of Tree-Width at Most Four, SIAM Journal on Discrete Mathematics, v.9 n.1, p.101-117, Feb. 1996 [doi>10.1137/S0895480193243043]
• 127: Isao Sasano , Zhenjiang Hu , Masato Takeichi , Mizuhito Ogawa, Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems, ACM SIGPLAN Notices, v.35 n.9, p.137-149, Sept. 2000
• 128: Satyanarayana, A. and Tung, L. 1990. A characterization of partial 3-trees. Netw. 20, 299--322.
• 129: 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.
• 130: Scheffler, P. 1988. What graphs have bounded treewidth? In Fischland Colloquium on Discrete Mathematics and Applications.
• 131: Scheffler, P. 1989. The treewidth of graphs as a measure for the complexity of algorithmic problems. Ph.D. thesis, German Academy of Sciences Berlin.
• 132: Scheffler, P. and Seese, D. 1986. Graphs of bounded tree-width and linear-time algorithms for NP-complete problems. In Bilateral Seminar.
• 133: P. Scheffler , Detlef Seese, A combinatorial and logical approach to linear-time computability, Proceedings of the European Conference on Computer Algebra, p.379-380, June 02-05, 1987
• 134: P. D. Seymour , Robin Thomas, Graph searching and a min-max theorem for tree-width, Journal of Combinatorial Theory Series B, v.58 n.1, p.22-33, May 1993 [doi>10.1006/jctb.1993.1027]
• 135: Seymour, P. and Thomas, R. 1994. Call routing and the ratcatcher. Combinatorica 14, 217--241.
• 136: Spinrad, J. 2003. Efficient Graph Representations. Fields Institute Monographs. AMS, Brooklyn, NY.
• 137: 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.
• 138: K. Takamizawa , T. Nishizeki , N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, Journal of the ACM (JACM), v.29 n.3, p.623-641, July 1982 [doi>10.1145/322326.322328]
• 139: Jan Arne Telle , Andrzej Proskurowski, Efficient sets in partial k-trees, Discrete Applied Mathematics, v.44 n.1-3, p.109-117, July 19, 1993 [doi>10.1016/0166-218X(93)90226-E]
• 140: Jan Arne Telle , Andrzej Proskurowski, Algorithms for Vertex Partitioning Problems on Partial k-Trees, SIAM Journal on Discrete Mathematics, v.10 n.4, p.529-550, 1997 [doi>10.1137/S0895480194275825]
• 141: Mikkel Thorup, All structured programs have small tree width and good register allocation, Information and Computation, v.142 n.2, p.159-181, May 2, 1998 [doi>10.1006/inco.1997.2697]
• 142: Valdes, J., Tarjan, R., and Lawler, E. 1982. The recognition of series parallel digraphs. SIAM J. Comput. 11, 298--313.
• 143: Vizing, V. 1964. On an estimate of the chromatic class of a p-graph. Discrete Anal. 3, 25--30.
• 144: Egon Wanke, k-NLC graphs and polynomial algorithms, Discrete Applied Mathematics, v.54 n.2-3, p.251-266, Oct. 17, 1994 [doi>10.1016/0166-218X(94)90026-4]
• 145: Thomas Victor Wimer , Stephen T. Hedetniemi, Linear algorithms on k-terminal graphs, Clemson University, Clemson, SC, 1987
• 146: Wimer, T. and Hedetniemi, S. 1988. K-terminal recursive families of graphs. Congressus Numer. 63, 161--176.
• 147: Wimer, T., Hedetniemi, S., and Laskar, R. 1985. A methodology for constructing linear graph algorithms. Congressus Numer. 50, 43--60.
• 148: Zhou, X., Fuse, K., and Nishizeki, T. 2000. A linear algorithm for finding {g,f}-colorings of partial k-trees. Algorithmica 27, 227--243.
• 149: 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.
• 150: Xiao Zhou , Shin-Ichi Nakano , Takao Nishizeki, A Linear Algorithm for Edge-Coloring Partial k-Trees, Proceedings of the First Annual European Symposium on Algorithms, p.409-418, September 30-October 02, 1993
• 151: Xiao Zhou , Shin-Ichi Nakano , Takao Nishizeki, Edge-coloring partial k-trees, Journal of Algorithms, v.21 n.3, p.598-617, Nov. 1996 [doi>10.1006/jagm.1996.0061]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Bandwidth, Halin graph, branchwidth, cliquewidth, cograph, cutwidth, dynamic programming, pathwidth, rankwidth, series parallel, tree, treewidth