# Approximation Algorithms for Maximally Balanced Connected Graph Partition

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2021-09-12

AUTHORS ABSTRACT

Given a connected graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document}, we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k≥4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 4$$\end{document}, no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3$$\end{document}. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. More... »

PAGES

3715-3740

### References to SciGraph publications

• 2020-02-17. Approximation algorithms for the maximally balanced connected graph tripartition problem in JOURNAL OF COMBINATORIAL OPTIMIZATION
• 2018-03-21. Efficient Algorithms for a Graph Partitioning Problem in FRONTIERS IN ALGORITHMICS
• 2013-01-03. Max-min weight balanced connected partition in JOURNAL OF GLOBAL OPTIMIZATION
• 2011. A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs in COMPUTATIONAL GEOMETRY, GRAPHS AND APPLICATIONS

TITLE

Algorithmica

ISSUE

12

VOLUME

83

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3

DOI

http://dx.doi.org/10.1007/s00453-021-00870-3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1141065848

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Yong",
"id": "sg:person.010555136403.19",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
],
"type": "Organization"
},
"familyName": "Lin",
"givenName": "Guohui",
"id": "sg:person.01130357621.02",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Georgia Southern University, Statesboro, USA",
"id": "http://www.grid.ac/institutes/grid.256302.0",
"name": [
"Department of Computer Science, Georgia Southern University, Statesboro, USA"
],
"type": "Organization"
},
"familyName": "Xu",
"givenName": "Yao",
"id": "sg:person.016633362253.49",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016633362253.49"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "An",
"id": "sg:person.015273653637.29",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/s10898-012-0028-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011271850",
"https://doi.org/10.1007/s10898-012-0028-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10878-020-00544-w",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1124916632",
"https://doi.org/10.1007/s10878-020-00544-w"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-24983-9_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035221403",
"https://doi.org/10.1007/978-3-642-24983-9_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-78455-7_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1101647685",
"https://doi.org/10.1007/978-3-319-78455-7_3"
],
"type": "CreativeWork"
}
],
"datePublished": "2021-09-12",
"datePublishedReg": "2021-09-12",
"description": "Given a connected graph G=(V,E)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G = (V, E)$$\\end{document}, we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k\u22654\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k \\ge 4$$\\end{document}, no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k\u22653\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k \\ge 3$$\\end{document}. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-021-00870-3",
"inLanguage": "en",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.8124106",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.7538013",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8898306",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8132243",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "12",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"k parts",
"min-max",
"graph partition",
"linear time exact algorithm",
"time exact algorithm",
"exact algorithm",
"approximability results",
"k-approximation",
"graph partition problem",
"approximation algorithm",
"connected graph",
"vertices",
"non-empty parts",
"partition",
"maximum cardinality",
"problem",
"algorithm",
"local improvement operations",
"partition problem",
"graph",
"part",
"subgraphs",
"cardinality",
"version",
"results",
"variants",
"purpose",
"improvement operations",
"more applications",
"applications",
"way",
"trees",
"operation",
"paper"
],
"name": "Approximation Algorithms for Maximally Balanced Connected Graph Partition",
"pagination": "3715-3740",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1141065848"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-021-00870-3"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-021-00870-3",
"https://app.dimensions.ai/details/publication/pub.1141065848"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:38",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_873.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-021-00870-3"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3'

This table displays all metadata directly associated to this object as RDF triples.

154 TRIPLES      22 PREDICATES      64 URIs      52 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N3feba179b4c64db4b8da30dd38a6cb2c
4 schema:citation sg:pub.10.1007/978-3-319-78455-7_3
5 sg:pub.10.1007/978-3-642-24983-9_19
6 sg:pub.10.1007/s10878-020-00544-w
7 sg:pub.10.1007/s10898-012-0028-8
8 schema:datePublished 2021-09-12
9 schema:datePublishedReg 2021-09-12
10 schema:description Given a connected graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document}, we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k≥4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 4$$\end{document}, no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3$$\end{document}. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.
11 schema:genre article
12 schema:inLanguage en
13 schema:isAccessibleForFree true
15 Nda7b8403361546fc87fb76f43f5664ae
16 sg:journal.1047644
17 schema:keywords algorithm
18 applications
19 approximability results
20 approximation algorithm
21 cardinality
22 connected graph
24 exact algorithm
25 graph
26 graph partition
27 graph partition problem
28 improvement operations
29 k parts
30 k-approximation
31 linear time exact algorithm
32 local improvement operations
33 maximum cardinality
34 min-max
35 more applications
36 non-empty parts
37 operation
38 paper
39 part
40 partition
41 partition problem
42 problem
43 purpose
44 results
45 subgraphs
46 time exact algorithm
47 trees
48 variants
49 version
50 vertices
51 way
52 schema:name Approximation Algorithms for Maximally Balanced Connected Graph Partition
53 schema:pagination 3715-3740
54 schema:productId N2ed16051a03f4f2ea5de1c9a23ac9451
55 Nf02e9b9101ce44a89a8f590d83978127
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1141065848
57 https://doi.org/10.1007/s00453-021-00870-3
58 schema:sdDatePublished 2022-05-20T07:38
60 schema:sdPublisher Nd6e45370fb4242b0bf7a7d99e86dfe71
61 schema:url https://doi.org/10.1007/s00453-021-00870-3
63 sgo:sdDataset articles
64 rdf:type schema:ScholarlyArticle
65 N07586dfdaa824c8d857090c278c3d4c5 rdf:first sg:person.01130357621.02
67 N2836f92f05d44056b5735defd450d1bc rdf:first sg:person.015273653637.29
68 rdf:rest rdf:nil
69 N2ed16051a03f4f2ea5de1c9a23ac9451 schema:name dimensions_id
70 schema:value pub.1141065848
71 rdf:type schema:PropertyValue
73 rdf:rest N2836f92f05d44056b5735defd450d1bc
74 N3f3d59f9ac7f4b7c8de36e70da8e98bd rdf:first sg:person.015654265661.98
75 rdf:rest N07586dfdaa824c8d857090c278c3d4c5
76 N3feba179b4c64db4b8da30dd38a6cb2c rdf:first sg:person.010555136403.19
77 rdf:rest N3f3d59f9ac7f4b7c8de36e70da8e98bd
79 rdf:type schema:PublicationVolume
80 Nd6e45370fb4242b0bf7a7d99e86dfe71 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Nda7b8403361546fc87fb76f43f5664ae schema:issueNumber 12
83 rdf:type schema:PublicationIssue
84 Nf02e9b9101ce44a89a8f590d83978127 schema:name doi
85 schema:value 10.1007/s00453-021-00870-3
86 rdf:type schema:PropertyValue
87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information and Computing Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
91 schema:name Computation Theory and Mathematics
92 rdf:type schema:DefinedTerm
93 sg:grant.7538013 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-021-00870-3
94 rdf:type schema:MonetaryGrant
95 sg:grant.8124106 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-021-00870-3
96 rdf:type schema:MonetaryGrant
97 sg:grant.8132243 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-021-00870-3
98 rdf:type schema:MonetaryGrant
99 sg:grant.8898306 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-021-00870-3
100 rdf:type schema:MonetaryGrant
101 sg:journal.1047644 schema:issn 0178-4617
102 1432-0541
103 schema:name Algorithmica
104 schema:publisher Springer Nature
105 rdf:type schema:Periodical
106 sg:person.010555136403.19 schema:affiliation grid-institutes:grid.411963.8
107 schema:familyName Chen
108 schema:givenName Yong
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
110 rdf:type schema:Person
111 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
112 schema:familyName Lin
113 schema:givenName Guohui
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
115 rdf:type schema:Person
116 sg:person.015273653637.29 schema:affiliation grid-institutes:grid.411963.8
117 schema:familyName Zhang
118 schema:givenName An
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29
120 rdf:type schema:Person
121 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
122 schema:familyName Chen
123 schema:givenName Zhi-Zhong
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
125 rdf:type schema:Person
126 sg:person.016633362253.49 schema:affiliation grid-institutes:grid.256302.0
127 schema:familyName Xu
128 schema:givenName Yao
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016633362253.49
130 rdf:type schema:Person
131 sg:pub.10.1007/978-3-319-78455-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101647685
132 https://doi.org/10.1007/978-3-319-78455-7_3
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/978-3-642-24983-9_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035221403
135 https://doi.org/10.1007/978-3-642-24983-9_19
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s10878-020-00544-w schema:sameAs https://app.dimensions.ai/details/publication/pub.1124916632
138 https://doi.org/10.1007/s10878-020-00544-w
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s10898-012-0028-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011271850
141 https://doi.org/10.1007/s10898-012-0028-8
142 rdf:type schema:CreativeWork
143 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
144 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
145 rdf:type schema:Organization
146 grid-institutes:grid.256302.0 schema:alternateName Department of Computer Science, Georgia Southern University, Statesboro, USA
147 schema:name Department of Computer Science, Georgia Southern University, Statesboro, USA
148 rdf:type schema:Organization
149 grid-institutes:grid.411963.8 schema:alternateName Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
150 schema:name Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
151 rdf:type schema:Organization
152 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Saitama, Japan
153 schema:name Division of Information System Design, Tokyo Denki University, Saitama, Japan
154 rdf:type schema:Organization