Ontology type: schema:ScholarlyArticle Open Access: True
2021-09-12
AUTHORSYong Chen, Zhi-Zhong Chen, Guohui Lin, Yao Xu, An Zhang
ABSTRACTGiven 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... »
PAGES3715-3740
http://scigraph.springernature.com/pub.10.1007/s00453-021-00870-3
DOIhttp://dx.doi.org/10.1007/s00453-021-00870-3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1141065848
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"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",
"volumeNumber": "83"
}
],
"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",
"decades",
"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",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"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"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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'
Turtle is a human-readable linked data format.
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