A Polynomial-Time Algorithm for Max-Min Partitioning of Ladders View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-08

AUTHORS

R. Becker, I. Lari, M. Lucertini, B. Simeone

ABSTRACT

Given a grid graph with two rows, an arbitrary number N of columns (briefly, a ladder ) and a weight function defined on its vertex set V , one wants to partition V into a given number p of connected components, so as to maximize the smallest weight of a component. We present an O(N4 pmax {p,log N}) -time algorithm, which combines dynamic programming with pre-processing and search techniques. An O(N) -time algorithm for the case p=2 is also given. In a companion paper [2] we show that the problem for a grid graph with three rows is NP-hard, and we give approximate algorithms for grid graphs with an arbitrary number of rows. More... »

PAGES

353-374

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-001-0008-8

DOI

http://dx.doi.org/10.1007/s00224-001-0008-8

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Cape Town", 
          "id": "https://www.grid.ac/institutes/grid.7836.a", 
          "name": [
            "Department of Mathematics, University of Cape Town,Rondebosch 7700, South Africa, ZA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Becker", 
        "givenName": "R.", 
        "id": "sg:person.010664424766.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010664424766.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Statistics,Italy, University of Rome ``La Sapienza'',Piazzale Aldo Moro 5, 00185 Rome,, IT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lari", 
        "givenName": "I.", 
        "id": "sg:person.014622102543.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014622102543.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Electrical Engineering, Italy, Centro Matematico Vito Volterra, University of Rome ``Tor Vergata'', Via O. Raimondo, 00173 Rome, IT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lucertini", 
        "givenName": "M.", 
        "id": "sg:person.07676374463.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676374463.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Statistics,Italy, University of Rome ``La Sapienza'',Piazzale Aldo Moro 5, 00185 Rome,, IT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "B.", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-08", 
    "datePublishedReg": "2001-08-01", 
    "description": "Given a grid graph with two rows, an arbitrary number N of columns (briefly, a ladder ) and a weight function defined on its vertex set V , one wants to partition V into a given number p of connected components, so as to maximize the smallest weight of a component. We present an O(N4 pmax {p,log N}) -time algorithm, which combines dynamic programming with pre-processing and search techniques. An O(N) -time algorithm for the case p=2 is also given. In a companion paper [2] we show that the problem for a grid graph with three rows is NP-hard, and we give approximate algorithms for grid graphs with an arbitrary number of rows.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-001-0008-8", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "34"
      }
    ], 
    "name": "A Polynomial-Time Algorithm for Max-Min Partitioning of Ladders", 
    "pagination": "353-374", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f8c01391d784b1db6bf0c373db76c5093e909fa0903cea78c71c2a9a52ba0472"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-001-0008-8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052221808"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-001-0008-8", 
      "https://app.dimensions.ai/details/publication/pub.1052221808"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T15:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8664_00000491.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-001-0008-8"
  }
]
 

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/s00224-001-0008-8'

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/s00224-001-0008-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-001-0008-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-001-0008-8'


 

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

88 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-001-0008-8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N120b27917d244ebbbea8bf1e4b0c2c14
4 schema:datePublished 2001-08
5 schema:datePublishedReg 2001-08-01
6 schema:description Given a grid graph with two rows, an arbitrary number N of columns (briefly, a ladder ) and a weight function defined on its vertex set V , one wants to partition V into a given number p of connected components, so as to maximize the smallest weight of a component. We present an O(N4 pmax {p,log N}) -time algorithm, which combines dynamic programming with pre-processing and search techniques. An O(N) -time algorithm for the case p=2 is also given. In a companion paper [2] we show that the problem for a grid graph with three rows is NP-hard, and we give approximate algorithms for grid graphs with an arbitrary number of rows.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N656522a153804c6884b2b888fbe1617c
11 Nc7f6b59c51174609b16e0e4826a5f660
12 sg:journal.1052098
13 schema:name A Polynomial-Time Algorithm for Max-Min Partitioning of Ladders
14 schema:pagination 353-374
15 schema:productId N38c756f5f1114d8598c248bcdaa5a9d0
16 Na22150c30fb24099b1866691a087e028
17 Nd0352a48db574e83a962c3331d7c887c
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052221808
19 https://doi.org/10.1007/s00224-001-0008-8
20 schema:sdDatePublished 2019-04-10T15:47
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nf55d2f69ba1b4c92aa3a567c08820ad1
23 schema:url http://link.springer.com/10.1007/s00224-001-0008-8
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N0a14a81a421c4bcda575cbcb12158a7c rdf:first sg:person.012600006066.78
28 rdf:rest rdf:nil
29 N120b27917d244ebbbea8bf1e4b0c2c14 rdf:first sg:person.010664424766.40
30 rdf:rest N1db41eb8dadf474d87395cf2b0f66bde
31 N1db41eb8dadf474d87395cf2b0f66bde rdf:first sg:person.014622102543.45
32 rdf:rest Na9466b96cba14ab2b8fe456fed10d5b1
33 N38c756f5f1114d8598c248bcdaa5a9d0 schema:name dimensions_id
34 schema:value pub.1052221808
35 rdf:type schema:PropertyValue
36 N42cada1bf56c430585d07ba2bf8cfd39 schema:name Department of Statistics,Italy, University of Rome ``La Sapienza'',Piazzale Aldo Moro 5, 00185 Rome,, IT
37 rdf:type schema:Organization
38 N656522a153804c6884b2b888fbe1617c schema:volumeNumber 34
39 rdf:type schema:PublicationVolume
40 N7e97ff11fab043debc697cdea7c88e8b schema:name Department of Statistics,Italy, University of Rome ``La Sapienza'',Piazzale Aldo Moro 5, 00185 Rome,, IT
41 rdf:type schema:Organization
42 Na22150c30fb24099b1866691a087e028 schema:name readcube_id
43 schema:value f8c01391d784b1db6bf0c373db76c5093e909fa0903cea78c71c2a9a52ba0472
44 rdf:type schema:PropertyValue
45 Na9466b96cba14ab2b8fe456fed10d5b1 rdf:first sg:person.07676374463.50
46 rdf:rest N0a14a81a421c4bcda575cbcb12158a7c
47 Nc7f6b59c51174609b16e0e4826a5f660 schema:issueNumber 4
48 rdf:type schema:PublicationIssue
49 Nd0352a48db574e83a962c3331d7c887c schema:name doi
50 schema:value 10.1007/s00224-001-0008-8
51 rdf:type schema:PropertyValue
52 Ndaeb93c5f1964e41a2a24cc5f3f8c7bb schema:name Department of Electrical Engineering, Italy, Centro Matematico Vito Volterra, University of Rome ``Tor Vergata'', Via O. Raimondo, 00173 Rome, IT
53 rdf:type schema:Organization
54 Nf55d2f69ba1b4c92aa3a567c08820ad1 schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computation Theory and Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1052098 schema:issn 1432-4350
63 1433-0490
64 schema:name Theory of Computing Systems
65 rdf:type schema:Periodical
66 sg:person.010664424766.40 schema:affiliation https://www.grid.ac/institutes/grid.7836.a
67 schema:familyName Becker
68 schema:givenName R.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010664424766.40
70 rdf:type schema:Person
71 sg:person.012600006066.78 schema:affiliation N42cada1bf56c430585d07ba2bf8cfd39
72 schema:familyName Simeone
73 schema:givenName B.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
75 rdf:type schema:Person
76 sg:person.014622102543.45 schema:affiliation N7e97ff11fab043debc697cdea7c88e8b
77 schema:familyName Lari
78 schema:givenName I.
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014622102543.45
80 rdf:type schema:Person
81 sg:person.07676374463.50 schema:affiliation Ndaeb93c5f1964e41a2a24cc5f3f8c7bb
82 schema:familyName Lucertini
83 schema:givenName M.
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676374463.50
85 rdf:type schema:Person
86 https://www.grid.ac/institutes/grid.7836.a schema:alternateName University of Cape Town
87 schema:name Department of Mathematics, University of Cape Town,Rondebosch 7700, South Africa, ZA
88 rdf:type schema:Organization
 




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


...