A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Bang Ye Wu

ABSTRACT

For a given graph with nonnegative weights on nodes, the max-min connected bipartition problem looks for a way to partition the graph into two connected subgraphs such that the minimum weight of the two subgraphs is maximized. In this paper, we give a polynomial time 7/6-approximation algorithm for grid graphs. The approximation ratio is currently the best result achieved in polynomial time. More... »

PAGES

188-194

Book

TITLE

Computational Geometry, Graphs and Applications

ISBN

978-3-642-24982-2
978-3-642-24983-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-24983-9_19

DOI

http://dx.doi.org/10.1007/978-3-642-24983-9_19

DIMENSIONS

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


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: 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": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "For a given graph with nonnegative weights on nodes, the max-min connected bipartition problem looks for a way to partition the graph into two connected subgraphs such that the minimum weight of the two subgraphs is maximized. In this paper, we give a polynomial time 7/6-approximation algorithm for grid graphs. The approximation ratio is currently the best result achieved in polynomial time.", 
    "editor": [
      {
        "familyName": "Akiyama", 
        "givenName": "Jin", 
        "type": "Person"
      }, 
      {
        "familyName": "Bo", 
        "givenName": "Jiang", 
        "type": "Person"
      }, 
      {
        "familyName": "Kano", 
        "givenName": "Mikio", 
        "type": "Person"
      }, 
      {
        "familyName": "Tan", 
        "givenName": "Xuehou", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-24983-9_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-24982-2", 
        "978-3-642-24983-9"
      ], 
      "name": "Computational Geometry, Graphs and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "grid graphs", 
      "bipartition problem", 
      "polynomial time", 
      "approximation ratio", 
      "connected subgraph", 
      "graph", 
      "algorithm", 
      "nonnegative weights", 
      "subgraphs", 
      "good results", 
      "minimum weight", 
      "nodes", 
      "way", 
      "time", 
      "results", 
      "weight", 
      "ratio", 
      "problem", 
      "paper", 
      "max-min connected bipartition problem", 
      "connected bipartition problem", 
      "polynomial time 7/6-approximation algorithm", 
      "time 7/6-approximation algorithm"
    ], 
    "name": "A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs", 
    "pagination": "188-194", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035221403"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-24983-9_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-24983-9_19", 
      "https://app.dimensions.ai/details/publication/pub.1035221403"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_418.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-24983-9_19"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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-642-24983-9_19'

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-642-24983-9_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-24983-9_19'

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-642-24983-9_19'


 

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

98 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-24983-9_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfe9d74d730094ac085fffd367cf11422
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description For a given graph with nonnegative weights on nodes, the max-min connected bipartition problem looks for a way to partition the graph into two connected subgraphs such that the minimum weight of the two subgraphs is maximized. In this paper, we give a polynomial time 7/6-approximation algorithm for grid graphs. The approximation ratio is currently the best result achieved in polynomial time.
7 schema:editor N4b2862b88a284e20b83b885e0f7ffa0a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N39419bf440414fe190e07a4dcfba8fbc
12 schema:keywords algorithm
13 approximation ratio
14 bipartition problem
15 connected bipartition problem
16 connected subgraph
17 good results
18 graph
19 grid graphs
20 max-min connected bipartition problem
21 minimum weight
22 nodes
23 nonnegative weights
24 paper
25 polynomial time
26 polynomial time 7/6-approximation algorithm
27 problem
28 ratio
29 results
30 subgraphs
31 time
32 time 7/6-approximation algorithm
33 way
34 weight
35 schema:name A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs
36 schema:pagination 188-194
37 schema:productId N4dae7378ddfe409bbc949a8ffa094008
38 N565173fae54049b0ae863510c534d27f
39 schema:publisher Nef2d86de1c85423d926f47ee5cb462c8
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035221403
41 https://doi.org/10.1007/978-3-642-24983-9_19
42 schema:sdDatePublished 2021-12-01T20:09
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nc4c8c4db6b3c435dae061772556afd23
45 schema:url https://doi.org/10.1007/978-3-642-24983-9_19
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N2abb2a8c75014f2a8395346271894f31 schema:familyName Tan
50 schema:givenName Xuehou
51 rdf:type schema:Person
52 N39419bf440414fe190e07a4dcfba8fbc schema:isbn 978-3-642-24982-2
53 978-3-642-24983-9
54 schema:name Computational Geometry, Graphs and Applications
55 rdf:type schema:Book
56 N4449f478cb5044ec8db12c3335727256 schema:familyName Kano
57 schema:givenName Mikio
58 rdf:type schema:Person
59 N4b2862b88a284e20b83b885e0f7ffa0a rdf:first N763c9c0a81f640e3a5d6f8268ce91b22
60 rdf:rest Ndfc69b0024e74e909dc651914d3a56f1
61 N4dae7378ddfe409bbc949a8ffa094008 schema:name dimensions_id
62 schema:value pub.1035221403
63 rdf:type schema:PropertyValue
64 N565173fae54049b0ae863510c534d27f schema:name doi
65 schema:value 10.1007/978-3-642-24983-9_19
66 rdf:type schema:PropertyValue
67 N67279c6c1ee84be5b61e50ed28ef5121 schema:familyName Bo
68 schema:givenName Jiang
69 rdf:type schema:Person
70 N763c9c0a81f640e3a5d6f8268ce91b22 schema:familyName Akiyama
71 schema:givenName Jin
72 rdf:type schema:Person
73 N9a934f938fa7433aa2b9dccb62b904b0 rdf:first N2abb2a8c75014f2a8395346271894f31
74 rdf:rest rdf:nil
75 Nc4c8c4db6b3c435dae061772556afd23 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Ndfc69b0024e74e909dc651914d3a56f1 rdf:first N67279c6c1ee84be5b61e50ed28ef5121
78 rdf:rest Nf65bb54da6384d819e632cfdfff7057c
79 Nef2d86de1c85423d926f47ee5cb462c8 schema:name Springer Nature
80 rdf:type schema:Organisation
81 Nf65bb54da6384d819e632cfdfff7057c rdf:first N4449f478cb5044ec8db12c3335727256
82 rdf:rest N9a934f938fa7433aa2b9dccb62b904b0
83 Nfe9d74d730094ac085fffd367cf11422 rdf:first sg:person.013045767237.23
84 rdf:rest rdf:nil
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
89 schema:name Computation Theory and Mathematics
90 rdf:type schema:DefinedTerm
91 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
92 schema:familyName Wu
93 schema:givenName Bang Ye
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
95 rdf:type schema:Person
96 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
97 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
98 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...