Approximation algorithms for maximum weighted internal spanning trees in regular graphs and subdivisions of graphs

被引:0
作者
Hakim, Sheikh Azizul [1 ]
Nishat, Rahnuma Islam [2 ]
Rahman, Md Saidur [1 ]
机构
[1] Bangladesh Univ Engn & Technol, Dept Comp Sci & Engn, Graph Drawing & Informat Visualizat Lab, Dhaka 1000, Bangladesh
[2] Brock Univ, Dept Comp Sci, St Catharines, ON L2S 3A1, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Approximation algorithms - Consensus algorithm - Hamiltonians - NP-hard - Trees (mathematics);
D O I
10.1093/comjnl/bxae055
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Let G be a vertex-weighted connected graph of n vertices and let T be a spanning tree of G. We call T a maximum weighted internal spanning tree of G if the sum of the weights of the internal vertices of T is the maximum over all spanning trees of G. The maximum weighted internal spanning tree (MaxwIST) problem asks to find such a spanning tree T of G. The problem is NP-hard. We give an O(dn) time approximation algorithm for d-regular graphs of n=vertical bar V vertical bar vertices that computes a spanning tree with total weight of the internal vertices is at least beta(d)/beta(d) + (d - 2) - epsilon of the total weight of all the vertices of the graph for any epsilon > 0, where beta(d) = (d-1)Hd-1, and Sigma(d-1)(i=1) i(-1) is the (d-1)th harmonic number. For every d >= 3 and n(0) >= 1, we show the construction of a d-regular graph of at least n(0) vertices, such that for any of its spanning trees, w(I)/w(V) <= d/d+1 holds. We give an O(dn) time approximation algorithm for subdivisions of d-regular graphs, where the ratio of the internal weight of the spanning tree with the total vertex weight of the graph is at least d-1/2d-3-epsilon for epsilon > 0. We extend our study to x-subdivisions of Hamiltonian and hypoHamiltonian graphs, where each edge of the original Hamiltonian or hypoHamiltonian graph has been subdivided at least x times. For those two graph classes, we show that there exists a spanning tree with internal vertex weight at least 1-2/x-1 of the total vertex weight of the graph. Furthermore, we give O(n) time algorithm for x-subdivisions of biconnected outerplanar graphs and 4-connected planar graphs to achieve the above bound.
引用
收藏
页码:2898 / 2905
页数:8
相关论文
共 50 条
[31]   The Number of Spanning Trees in 4-Regular Simple Graphs [J].
Sereni, Jean-Sebastien ;
Yilma, Zelealem B. .
ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (04)
[32]   A simple upper bound for the number of spanning trees of regular graphs [J].
Voblyi, V. A. .
DISCRETE MATHEMATICS AND APPLICATIONS, 2008, 18 (04) :363-366
[33]   Edge-disjoint spanning trees and eigenvalues of regular graphs [J].
Cioaba, Sebastian M. ;
Wong, Wiseley .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 437 (02) :630-647
[34]   A simple upper bound for the number of spanning trees of regular graphs [J].
Discrete Math Appl, 2008, 4 (363-366)
[35]   Weighted spanning trees on some self-similar graphs [J].
D'Angeli, Daniele ;
Donno, Alfredo .
ELECTRONIC JOURNAL OF COMBINATORICS, 2011, 18 (01)
[36]   Heavy cycles and spanning trees with few leaves in weighted graphs [J].
Li, Binlong ;
Zhang, Shenggui .
APPLIED MATHEMATICS LETTERS, 2011, 24 (06) :908-910
[37]   Diameter-Preserving Spanning Trees in Sparse Weighted Graphs [J].
Yue Liu ;
Jing Huang .
Graphs and Combinatorics, 2009, 25 :753-758
[38]   Non-uniform random spanning trees on weighted graphs [J].
Mosbah, M ;
Saheb, N .
THEORETICAL COMPUTER SCIENCE, 1999, 218 (02) :263-271
[39]   A new technique for the characterization of graphs, with a maximum number of spanning trees [J].
Petingi, L ;
Rodriguez, J .
DISCRETE MATHEMATICS, 2002, 244 (1-3) :351-373
[40]   On the asymptotic behavior of the maximum number of spanning trees in circulant graphs [J].
Lonc, Z ;
Parol, K ;
Wojciechowski, JM .
NETWORKS, 1997, 30 (01) :47-56