Premium
The degree‐preserving spanning tree problem in strongly chordal and directed path graphs
Author(s) -
Lin ChingChi,
Chang Gerard J.,
Chen GenHuey
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20359
Subject(s) - combinatorics , spanning tree , mathematics , shortest path tree , degree (music) , minimum degree spanning tree , minimum spanning tree , vertex (graph theory) , chordal graph , ackermann function , tree (set theory) , trémaux tree , discrete mathematics , inverse , graph , pathwidth , line graph , physics , geometry , acoustics
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