Technical Report CS0784

TR#:CS0784
Class:CS
Title: OPTIMAL SPANNERS IN PARTIAL k-TREES.
Authors: J. A. Makowsky and U. Rotics
PDFCS0784.pdf
Abstract:

Assume you have a problem K which is NP-hard in general, but in P for a certain class of graphs G. Let Patch_G be a class of graphs which are `patched' together from graphs from G. is membership in K \cap Patch_G now in P? We show that for K_t, the problem of finding optimal t-spanners, G certain families of cliques and Patch_G the partial k-trees or the clique sequence graphs (here for 2-spanners only), this is the case. For the case of partial k-trees we use a method first proposed by Arnborg and Proskurowski. The clique sequence graphs are newly introduced in this paper. The choice of the problem of finding t-spanners was motivated by its application in distributed systems, communication networks, parallel architectures and motion planning, among others.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0784), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin