# Approximation Algorithms for Maximally Balanced Connected Graph Partition

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2019-11-23

AUTHORS ABSTRACT

Given a simple connected graph \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 general 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; but no approximability result exists for k-BGP when \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}, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any constant \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 be useful for related graph partition problems. More... »

PAGES

130-141

### Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-030-36411-3
978-3-030-36412-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_11

DOI

http://dx.doi.org/10.1007/978-3-030-36412-0_11

DIMENSIONS

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

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, Edmonton, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, Edmonton, 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, Kettering University, Flint, MI, USA",
"id": "http://www.grid.ac/institutes/grid.258550.f",
"name": [
"Department of Computer Science, Kettering University, Flint, MI, 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"
}
],
"datePublished": "2019-11-23",
"datePublishedReg": "2019-11-23",
"description": "Given a simple connected graph \\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 general 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; but no approximability result exists for k-BGP when \\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}, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any constant \\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 be useful for related graph partition problems.",
"editor": [
{
"familyName": "Li",
"givenName": "Yingshu",
"type": "Person"
},
{
"familyName": "Cardei",
"givenName": "Mihaela",
"type": "Person"
},
{
"familyName": "Huang",
"givenName": "Yan",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-030-36412-0_11",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-030-36411-3",
"978-3-030-36412-0"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"graph partition",
"graph partition problem",
"simple connected graph",
"k parts",
"linear time exact algorithm",
"time exact algorithm",
"approximability results",
"approximation algorithm",
"connected graph",
"maximum cardinality",
"min-max",
"exact algorithm",
"k-approximation",
"partition problem",
"cardinality",
"problem",
"algorithm",
"graph",
"vertices",
"non-empty parts",
"subgraphs",
"partition",
"local improvement operations",
"improvement operations",
"version",
"part",
"way",
"results",
"operation",
"trees",
"purpose",
"paper"
],
"name": "Approximation Algorithms for Maximally Balanced Connected Graph Partition",
"pagination": "130-141",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1123159174"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-030-36412-0_11"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-030-36412-0_11",
"https://app.dimensions.ai/details/publication/pub.1123159174"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:48",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_50.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-030-36412-0_11"
}
]

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/978-3-030-36412-0_11'

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/978-3-030-36412-0_11'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_11'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_11'

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

140 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N2d2b07ccb3ab4fbcb6149c4dc795a6bf
4 schema:datePublished 2019-11-23
5 schema:datePublishedReg 2019-11-23
6 schema:description Given a simple connected graph \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 general 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; but no approximability result exists for k-BGP when \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}, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any constant \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 be useful for related graph partition problems.
7 schema:editor N5f4722a6f30a49f291ccc4440e6b5232
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne170c378b85b45b88f0fde01cea8fb66
12 schema:keywords algorithm
13 approximability results
14 approximation algorithm
15 cardinality
16 connected graph
18 exact algorithm
19 graph
20 graph partition
21 graph partition problem
22 improvement operations
23 k parts
24 k-approximation
25 linear time exact algorithm
26 local improvement operations
27 maximum cardinality
28 min-max
29 non-empty parts
30 operation
31 paper
32 part
33 partition
34 partition problem
35 problem
36 purpose
37 results
38 simple connected graph
39 subgraphs
40 time exact algorithm
41 trees
42 version
43 vertices
44 way
45 schema:name Approximation Algorithms for Maximally Balanced Connected Graph Partition
46 schema:pagination 130-141
47 schema:productId N845c6fd28e694028a9a2bf4e38710855
48 Ne258c9a451f0423092d4641b709ce3b1
49 schema:publisher Nfae8df11aab346b7bea063075d0168c1
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1123159174
51 https://doi.org/10.1007/978-3-030-36412-0_11
52 schema:sdDatePublished 2022-05-20T07:48
54 schema:sdPublisher N825f78818bf14945b325a6534519426a
55 schema:url https://doi.org/10.1007/978-3-030-36412-0_11
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N133ae606afae48aeb8c8d6ff895db82c rdf:first sg:person.01130357621.02
60 rdf:rest Nffc46930b9a2406cafde2018cc02ea93
61 N2d2b07ccb3ab4fbcb6149c4dc795a6bf rdf:first sg:person.010555136403.19
62 rdf:rest Na0d09f00119542ca845478e9110c4188
63 N2f071a2ff9df4ce6b7c7c560c6e3b8dc schema:familyName Cardei
64 schema:givenName Mihaela
65 rdf:type schema:Person
67 rdf:rest rdf:nil
68 N5f4722a6f30a49f291ccc4440e6b5232 rdf:first Nf12c05c0fa7f491b8980aea1391a5114
69 rdf:rest N96dddc2e7e4242c6ac8af535c298692e
71 schema:givenName Yan
72 rdf:type schema:Person
73 N825f78818bf14945b325a6534519426a schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N845c6fd28e694028a9a2bf4e38710855 schema:name doi
76 schema:value 10.1007/978-3-030-36412-0_11
77 rdf:type schema:PropertyValue
78 N96dddc2e7e4242c6ac8af535c298692e rdf:first N2f071a2ff9df4ce6b7c7c560c6e3b8dc
79 rdf:rest N2fc934b29ddc42f2946bc08229fd2c2b
80 Na0d09f00119542ca845478e9110c4188 rdf:first sg:person.015654265661.98
81 rdf:rest N133ae606afae48aeb8c8d6ff895db82c
82 Ne05d0bb857144118869d8066f2e812e9 rdf:first sg:person.015273653637.29
83 rdf:rest rdf:nil
84 Ne170c378b85b45b88f0fde01cea8fb66 schema:isbn 978-3-030-36411-3
85 978-3-030-36412-0
86 schema:name Combinatorial Optimization and Applications
87 rdf:type schema:Book
88 Ne258c9a451f0423092d4641b709ce3b1 schema:name dimensions_id
89 schema:value pub.1123159174
90 rdf:type schema:PropertyValue
91 Nf12c05c0fa7f491b8980aea1391a5114 schema:familyName Li
92 schema:givenName Yingshu
93 rdf:type schema:Person
94 Nfae8df11aab346b7bea063075d0168c1 schema:name Springer Nature
95 rdf:type schema:Organisation
96 Nffc46930b9a2406cafde2018cc02ea93 rdf:first sg:person.016633362253.49
97 rdf:rest Ne05d0bb857144118869d8066f2e812e9
98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
99 schema:name Information and Computing Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
102 schema:name Computation Theory and Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.010555136403.19 schema:affiliation grid-institutes:grid.411963.8
105 schema:familyName Chen
106 schema:givenName Yong
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
108 rdf:type schema:Person
109 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
110 schema:familyName Lin
111 schema:givenName Guohui
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
113 rdf:type schema:Person
114 sg:person.015273653637.29 schema:affiliation grid-institutes:grid.411963.8
115 schema:familyName Zhang
116 schema:givenName An
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29
118 rdf:type schema:Person
119 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
120 schema:familyName Chen
121 schema:givenName Zhi-Zhong
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
123 rdf:type schema:Person
124 sg:person.016633362253.49 schema:affiliation grid-institutes:grid.258550.f
125 schema:familyName Xu
126 schema:givenName Yao
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016633362253.49
128 rdf:type schema:Person
129 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, Edmonton, Canada
130 schema:name Department of Computing Science, University of Alberta, Edmonton, Canada
131 rdf:type schema:Organization
132 grid-institutes:grid.258550.f schema:alternateName Department of Computer Science, Kettering University, Flint, MI, USA
133 schema:name Department of Computer Science, Kettering University, Flint, MI, USA
134 rdf:type schema:Organization
135 grid-institutes:grid.411963.8 schema:alternateName Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
136 schema:name Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
137 rdf:type schema:Organization
138 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Saitama, Japan
139 schema:name Division of Information System Design, Tokyo Denki University, Saitama, Japan
140 rdf:type schema:Organization