Primal dual based algorithm for degree-balanced spanning tree problem

Yingli Ran

doi:10.1016/j.amc.2017.08.016

Primal dual based algorithm for degree-balanced spanning tree problem

2018-01-01

2

PRE

AI

DOI：10.1016/j.amc.2017.08.016

原文链接

原文求助

摘要

En 中文

This paper studies approximation algorithm for the degree-balanced spanning tree (DBST) problem. Given a graph G = (V, E), the goal is to find a spanning tree T such that Sigma v is an element of V deg(T)(v)(2) is minimized, where deg T (v) denotes the degree of node v in tree T. The idea of taking squares on node degrees is to manifest the role of nodes with large degree, and thus minimizing the sum will result in a comparatively balanced degree distribution. This is a non-linear objective function. We prove that DBST is NP-hard, and then develop a primal-dual based algorithm with a guaranteed performance ratio. (C) 2017 Elsevier Inc. All rights reserved.

Keyword:

Degree-balanced spanning tree

Nonlinear objective function

Primal dual algorithm

Primal dual based algorithm for degree-balanced spanning tree problem

摘要

AI总结

期刊

机构

引用论文