Linear-time computation of optimal subgraphs of decomposable graphs. (English) Zbl 0618.68058

Bern, M. W.; Lawler, E. L.; Wong, A. L.

J. Algorithms 8, 216-235 (1987).

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is ”regular” with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain a linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C35	Programming involving graphs or networks

Keywords:

combinatorial optimization; computational graph theory; weighted graph; matching; traveling salesman; linear-time algorithms; irredundance number of a tree