返回Google圖書搜尋

Spanners in Graphs with Bounded Degree

出版	University of Saskatchewan, Department of Computational Science, 1993
URL	http://books.google.com.hk/books?id=hVLLpwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Given a graph G = (V, E), a subgraph S = (V, E[subscript S]) is a t-spanner of G if for every edge xy [element of] E, the distance between x and y in S is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum size t-spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum size 2-spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a 'triangle- free component' and 'triangular-components'. On the other hand, it is shown that to determine whether a graph with maximum degree at least nine contains a t-spanner with at most K edges (K is given) is NP-complete for any fixed t [> or =] 2."