Regularity and locality in \(k\)-terminal graphs.

*(English)*Zbl 0822.68084Summary: M. W. Bern, E. L. Lawler and A. L. Wong J. Algorithms 8, 216-235 (1987; Zbl 0618.68058) described a general method for constructing algorithms to find an optimal subgraph in a given graph. When the given graph is a member of a \(k\)-terminal recursive family of graphs and is presented in the form of a parse tree, and when the optimal subgraph satisfies a property that is regular with respect to the family of graphs, then the method produces a linear-time algorithm. The algorithms assume the existence of multiplication tables that are specific to the regular property and to the family of graphs. In this paper we show that the general problem of computing these multiplication tables is unsolvable and provide a “pumping” lemma for proving that particular properties are not regular for particular \(k\)-terminal families. In contrast with these negative results, we show that all local properties, that can be verified by examining a bounded neighbourhood of each vertex in a graph, are regular with respect to all \(k\)-terminal recursive families of graphs, and we show how to automate the construction of the multiplication tables for any local property.

Reviewer: Reviewer (Berlin)

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

05C05 | Trees |

05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |

##### Keywords:

regular graph properties; \(k\)-terminal recursive graphs; parse tree; linear-time algorithm
PDF
BibTeX
XML
Cite

\textit{S. Mahajan} and \textit{J. G. Peters}, Discrete Appl. Math. 54, No. 2--3, 229--250 (1994; Zbl 0822.68084)

Full Text:
DOI

##### References:

[1] | Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposibilityâ€”a survey, Bit, 25, 2-33, (1985) |

[2] | Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 277-284, (1987) · Zbl 0611.05022 |

[3] | Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, (), 38-51, Lecture Notes in Computer Science |

[4] | Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. algebraic discrete methods, 7, 305-314, (1986) · Zbl 0597.05027 |

[5] | Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067 |

[6] | Bern, M.W.; Lawler, E.L.; Wong, A.L.; Bern, M.W.; Lawler, E.L.; Wong, A.L., Preliminary version appeared as why certain subgraph computations require only linear time, J. algorithms, Proceedings of the 26th IEEE symposium on foundations of computer science, 8, 117-125, (1985) |

[7] | Bodlaender, H.L.; Bodlaender, H.L., Dynamic programming on graphs with bounded tree-width, (), Tech. report RUU-CS-87-22, 105-118, (1987), Department of Computer Science, University of Utrecht Netherlands, Also see |

[8] | Borie, R.B.; Parker, R.G.; Tovey, C.A., Automatic generation of linear algorithms from predicate calculus descriptions of problems of recursively constructed graph families, (1988), Georgia Institute of Technology, manuscript · Zbl 0753.05062 |

[9] | Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and comput., 85, 12-75, (1990) · Zbl 0722.03008 |

[10] | Hedetniemi, S.T., Bibliography of algorithms on partial k-trees, (1989), manuscript |

[11] | Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA, Ch. 8 · Zbl 0196.01701 |

[12] | Mahajan, S.; Peters, J.G.; Mahajan, S.; Peters, J.G., Algorithms for regular properties in recursive graphs, Proceedings of the 25th allerton conference on communication, control, and computing, Tech. report TR 87-7, 14-23, (1987), School of Computing Science, Simon Fraser University |

[13] | Seese, D., Tree-partite graphs and the complexity of algorithms, (), 412-421, Proceedings, Lecture Notes in Computer Science · Zbl 0574.68036 |

[14] | Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series – parallel graphs, J. ACM, 29, 623-641, (1982) · Zbl 0485.68055 |

[15] | Wimer, T.V., Linear algorithms on k-terminal graphs, Ph.D. thesis, (1987), Clemson University Clemson, SC · Zbl 0669.05050 |

[16] | Wimer, T.V.; Hedetniemi, S.T.; Laskar, R., A methodology for constructing linear graph algorithms, Congr. numer., 50, 43-60, (1985) · Zbl 0603.68040 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.