The degree-preserving spanning tree problem in strongly chordal and directed path graphs
Journal
Networks
Journal Volume
56
Journal Issue
3
Pages
183-187
Date Issued
2010
Author(s)
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.
Type
journal article