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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom