The degree-preserving spanning tree problem in strongly chordal and directed path graphs
✍ Scribed by Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 108 KB
- Volume
- 56
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Suppose G is a connected graph and T a spanning tree of G. A vertex v ε V(G) is said to be a degree‐preserving vertex if its degree in T is the same as its degree in G. The degree‐preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree‐preserving vertices is maximized. The purpose of this article is to provide an O(m.α(m,n))‐time algorithm for the degree‐preserving spanning tree problem in strongly chordal graphs, where α is the inverse of Ackermann's function. Furthermore, we present an O(m + n)‐time algorithm in directed path graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010