Parametric computing deals with problems where the input is a function of one or more parameters. This research will analyze various questions in parametric combinatorial optimization. These questions can be described as either search or construction problems. Search problems involve finding the parameter values for which certain conditions hold. Construction problems deal with determining the set of all the optimum solutions that are obtained when varying the parameters within a prescribed range. Three specific areas of research are: Parametric optimum subgraph problems on graphs of bounded treewidth; Efficient combinatorial algorithms for Lagranian relaxation problems; Implementation of construction and search algorithms, especially for problems related to minimum spanning trees. A common theme is the notion of algorithm simulation, a technique that originated in the field of minimum-ratio optimization. This work combines this idea with other algorithmic, geometrical, and graph-theoretical tools.
