Primal dual based algorithm for degree-balanced spanning tree problem

Yingli Ran; Zhihao Chen; Shaojie Tang; Zhao Zhang

doi:10.1016/j.amc.2017.08.016

Primal dual based algorithm for degree-balanced spanning tree problem

Yingli Ran
, Zhihao Chen
, Shaojie Tang
, Zhao Zhang

Management Science and Systems

Xinjiang University
Zhejiang Normal University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 ∑_{v ∈ V}deg_T(v)² 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.

Original language	English
Pages (from-to)	167-173
Number of pages	7
Journal	Applied Mathematics and Computation
Volume	316
DOIs	https://doi.org/10.1016/j.amc.2017.08.016
State	Published - Jan 1 2018

Keywords

Degree-balanced spanning tree
Nonlinear objective function
Primal dual algorithm

Access to Document

10.1016/j.amc.2017.08.016

Cite this

@article{f6a014f0392346b6ba4172a4c3a8efd5,

title = "Primal dual based algorithm for degree-balanced spanning tree problem",

abstract = "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 ∑v ∈ VdegT(v)2 is minimized, where degT(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{\textendash}dual based algorithm with a guaranteed performance ratio.",

keywords = "Degree-balanced spanning tree, Nonlinear objective function, Primal dual algorithm",

author = "Yingli Ran and Zhihao Chen and Shaojie Tang and Zhao Zhang",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2018",

month = jan,

day = "1",

doi = "10.1016/j.amc.2017.08.016",

language = "English",

volume = "316",

pages = "167--173",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Primal dual based algorithm for degree-balanced spanning tree problem

AU - Ran, Yingli

AU - Chen, Zhihao

AU - Tang, Shaojie

AU - Zhang, Zhao

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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 ∑v ∈ VdegT(v)2 is minimized, where degT(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.

AB - 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 ∑v ∈ VdegT(v)2 is minimized, where degT(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.

KW - Degree-balanced spanning tree

KW - Nonlinear objective function

KW - Primal dual algorithm

UR - https://www.scopus.com/pages/publications/85028564927

U2 - 10.1016/j.amc.2017.08.016

DO - 10.1016/j.amc.2017.08.016

M3 - Article

AN - SCOPUS:85028564927

SN - 0096-3003

VL - 316

SP - 167

EP - 173

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

ER -

Primal dual based algorithm for degree-balanced spanning tree problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this