Approximation algorithms for the maximally balanced connected graph tripartition problem

Guangting Chen (), Yong Chen (), Zhi-Zhong Chen (), Guohui Lin (), Tian Liu () and An Zhang ()
Additional contact information
Guangting Chen: Taizhou University
Yong Chen: Hangzhou Dianzi University
Zhi-Zhong Chen: Tokyo Denki University
Guohui Lin: University of Alberta
Tian Liu: Peking University
An Zhang: Hangzhou Dianzi University

Journal of Combinatorial Optimization, No 0, 21 pages

Abstract: Abstract Given a vertex-weighted connected graph $$G = (V, E, w(\cdot ))$$G=(V,E,w(·)), the maximally balanced connected graphk-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max–mink-BGP (min–maxk-BGP, respectively), and has received much study since about four decades ago. On general graphs, max–mink-BGP is strongly NP-hard for every fixed $$k \ge 2$$k≥2, and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max–min BGP, and cannot be approximated within 6/5 unless P $$=$$= NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min–max 3-BGP and a 5/3-approximation for max–min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge.

Keywords: Graph partition; Induced subgraph; Connected component; 2-connected component; Approximation algorithm (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00544-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00544-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00544-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().