Why Certain Subgraph Computations Require Only Linear Time

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 present a general methodology for constructing linear time algorithms in the case that 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 "regular" property (such as independence or matching). This methodology 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.

Authors

• Marshall W. Bern
• Eugene L. Lawler
• A. L. Wong

Keywords

• Tree graphs
• Traveling salesman problems
• Polynomials
• Steiner trees
• Computer science
• Graph theory
• Linear Time
• Linear Algorithm
• Polynomial-time Algorithm
• Series Of Analogues
• Matching Problem
• Traveling Salesman Problem
• Composition Rules
• Linear-time Algorithm
• Set Of Equations
• Independent Set
• Dynamic Programming
• State Machine
• Subtree
• Representative Class
• Homomorphism
• Range Of Classes
• Set Of Graphs
• Dynamic Programming Algorithm
• Maximum Matching
• Class Of Graphs
• Composition Operator
• Regularity Properties
• Subset Of Pairs
• Single Vertex
• Maximum Independent Set
• Inner Nodes
• Regular Set
• Proof Of Theorem
• Problem In Networks