Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2012-03-31

AUTHORS

Bang Ye Wu

ABSTRACT

For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP2) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP2 problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP2 problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows. More... »

PAGES

592-607

References to SciGraph publications

  • 1977-09. A homology theory for spanning tress of a graph in ACTA MATHEMATICA HUNGARICA
  • 1996-09. Highly linked graphs in COMBINATORICA
  • 2001-01-01. A Polynomial-Time Algorithm for Max-Min Partitioning of Ladders in THEORY OF COMPUTING SYSTEMS
  • 2003-04. Graph Connectivity After Path Removal in COMBINATORICA
  • 2005-04. Non-Separating Paths in 4-Connected Graphs in ANNALS OF COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-012-9481-z

    DOI

    http://dx.doi.org/10.1007/s10878-012-9481-z

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Chung Cheng University, Minhsiung, Chia Yi, Taiwan 621, ROC", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "National Chung Cheng University, Minhsiung, Chia Yi, Taiwan 621, ROC"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00224-001-0008-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052221808", 
              "https://doi.org/10.1007/s00224-001-0008-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00026-005-0240-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035845238", 
              "https://doi.org/10.1007/s00026-005-0240-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s003-0018-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042212243", 
              "https://doi.org/10.1007/s003-0018-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01261316", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028669841", 
              "https://doi.org/10.1007/bf01261316"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01896190", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050830116", 
              "https://doi.org/10.1007/bf01896190"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012-03-31", 
        "datePublishedReg": "2012-03-31", 
        "description": "For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP2) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP2 problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP2 problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10878-012-9481-z", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "26"
          }
        ], 
        "keywords": [
          "grid graphs", 
          "exact algorithm", 
          "bipartition problem", 
          "minimum weight path", 
          "polynomial time approximation scheme", 
          "pair of nodes", 
          "time approximation scheme", 
          "approximation scheme", 
          "polynomial time", 
          "path problem", 
          "connected subgraph", 
          "algorithm", 
          "graph", 
          "nodes", 
          "number of rows", 
          "scheme", 
          "path", 
          "positive weights", 
          "subgraphs", 
          "technique", 
          "time", 
          "way", 
          "best ratio", 
          "number", 
          "rows", 
          "results", 
          "pairs", 
          "weight", 
          "ratio", 
          "problem", 
          "paper", 
          "minimum non-separating path problem", 
          "non-separating path problem", 
          "weight path", 
          "balanced connected bipartition (BCP2) problem", 
          "connected bipartition (BCP2) problem", 
          "minimum weight non-separating path", 
          "weight non-separating path", 
          "non-separating path", 
          "BCP2 problem", 
          "minimum non-separating path"
        ], 
        "name": "Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs", 
        "pagination": "592-607", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015142435"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-012-9481-z"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-012-9481-z", 
          "https://app.dimensions.ai/details/publication/pub.1015142435"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:28", 
        "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/article/article_580.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10878-012-9481-z"
      }
    ]
     

    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/s10878-012-9481-z'

    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/s10878-012-9481-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-012-9481-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-012-9481-z'


     

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

    127 TRIPLES      22 PREDICATES      73 URIs      58 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-012-9481-z schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N09944e3bd0da48859495ae46d45e46a5
    6 schema:citation sg:pub.10.1007/bf01261316
    7 sg:pub.10.1007/bf01896190
    8 sg:pub.10.1007/s00026-005-0240-4
    9 sg:pub.10.1007/s00224-001-0008-8
    10 sg:pub.10.1007/s003-0018-z
    11 schema:datePublished 2012-03-31
    12 schema:datePublishedReg 2012-03-31
    13 schema:description For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP2) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP2 problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP2 problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Nc6d900d46f204929ae402e85a36252b9
    18 Nc7e2614cb24a475fbb224e430d6bbcf4
    19 sg:journal.1036683
    20 schema:keywords BCP2 problem
    21 algorithm
    22 approximation scheme
    23 balanced connected bipartition (BCP2) problem
    24 best ratio
    25 bipartition problem
    26 connected bipartition (BCP2) problem
    27 connected subgraph
    28 exact algorithm
    29 graph
    30 grid graphs
    31 minimum non-separating path
    32 minimum non-separating path problem
    33 minimum weight non-separating path
    34 minimum weight path
    35 nodes
    36 non-separating path
    37 non-separating path problem
    38 number
    39 number of rows
    40 pair of nodes
    41 pairs
    42 paper
    43 path
    44 path problem
    45 polynomial time
    46 polynomial time approximation scheme
    47 positive weights
    48 problem
    49 ratio
    50 results
    51 rows
    52 scheme
    53 subgraphs
    54 technique
    55 time
    56 time approximation scheme
    57 way
    58 weight
    59 weight non-separating path
    60 weight path
    61 schema:name Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
    62 schema:pagination 592-607
    63 schema:productId N4ba4232be2924fa1b5b83fd9e2af3a5d
    64 Nc1610779b6ab4d31ba7958995c9025c8
    65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015142435
    66 https://doi.org/10.1007/s10878-012-9481-z
    67 schema:sdDatePublished 2021-12-01T19:28
    68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    69 schema:sdPublisher N6bff7cb0db354274b2a777fff14eab65
    70 schema:url https://doi.org/10.1007/s10878-012-9481-z
    71 sgo:license sg:explorer/license/
    72 sgo:sdDataset articles
    73 rdf:type schema:ScholarlyArticle
    74 N09944e3bd0da48859495ae46d45e46a5 rdf:first sg:person.013045767237.23
    75 rdf:rest rdf:nil
    76 N4ba4232be2924fa1b5b83fd9e2af3a5d schema:name doi
    77 schema:value 10.1007/s10878-012-9481-z
    78 rdf:type schema:PropertyValue
    79 N6bff7cb0db354274b2a777fff14eab65 schema:name Springer Nature - SN SciGraph project
    80 rdf:type schema:Organization
    81 Nc1610779b6ab4d31ba7958995c9025c8 schema:name dimensions_id
    82 schema:value pub.1015142435
    83 rdf:type schema:PropertyValue
    84 Nc6d900d46f204929ae402e85a36252b9 schema:volumeNumber 26
    85 rdf:type schema:PublicationVolume
    86 Nc7e2614cb24a475fbb224e430d6bbcf4 schema:issueNumber 3
    87 rdf:type schema:PublicationIssue
    88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Mathematical Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Pure Mathematics
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Applied Mathematics
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Numerical and Computational Mathematics
    99 rdf:type schema:DefinedTerm
    100 sg:journal.1036683 schema:issn 1382-6905
    101 1573-2886
    102 schema:name Journal of Combinatorial Optimization
    103 schema:publisher Springer Nature
    104 rdf:type schema:Periodical
    105 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
    106 schema:familyName Wu
    107 schema:givenName Bang Ye
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
    109 rdf:type schema:Person
    110 sg:pub.10.1007/bf01261316 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028669841
    111 https://doi.org/10.1007/bf01261316
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/bf01896190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050830116
    114 https://doi.org/10.1007/bf01896190
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/s00026-005-0240-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035845238
    117 https://doi.org/10.1007/s00026-005-0240-4
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/s00224-001-0008-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052221808
    120 https://doi.org/10.1007/s00224-001-0008-8
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/s003-0018-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1042212243
    123 https://doi.org/10.1007/s003-0018-z
    124 rdf:type schema:CreativeWork
    125 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, Minhsiung, Chia Yi, Taiwan 621, ROC
    126 schema:name National Chung Cheng University, Minhsiung, Chia Yi, Taiwan 621, ROC
    127 rdf:type schema:Organization
     




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


    ...