On some problems on K-trees and partial K-trees

The objective of this thesis is to investigate some structural and algorithmic properties of k-trees and partial k-trees.;In Chapter 2 of the thesis we analyze a fixed cost spanning forest (FCSF) problem, defined over a graph G. We develop a linear time algorithm for solving the FCSF problem a series-parallel network. We further analyze a related cost allocation problem. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be verified in polynomial time, for the nonemptiness of the core of this game.;In Chapter 3, we develop a linear time algorithm to solve single source shortest path problem. We also compute the diameter of a k-tree with equal edge lengths in linear time, and construct an O(;In Chapter 4 we present a new characterization of a k-path between two vertices u and v, in an equal weight k-tree G. We use it to develop an O(;In Chapter 5 we prove the existence of a k-separator in a partial k-tree graph and construct a linear time algorithm that finds such a separator in k-trees. This algorithm can be used to obtain a balanced binary decomposition of a k-tree in O(n log n) time. Finally, we construct NC algorithms for the recognition of a partial k-tree for k = 2 and 3, which run in O(...