Shortest path length with bounded-alternation (min,+) formulas View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-09-10

AUTHORS

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

ABSTRACT

We study bounded-depth (min,+) formulas computing the shortest path polynomial. For depth 2d with d≥2, we obtain lower bounds parameterized by certain fan-in restrictions on + gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight.

PAGES

1-7

References to SciGraph publications

  • 2015-07. Lower Bounds for Tropical Circuits and Dynamic Programs in THEORY OF COMPUTING SYSTEMS
  • 2014-06. Limitations of Incremental Dynamic Programming in ALGORITHMICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s12572-018-0229-6

    DOI

    http://dx.doi.org/10.1007/s12572-018-0229-6

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Mathematical Sciences", 
              "id": "https://www.grid.ac/institutes/grid.462414.1", 
              "name": [
                "The Institute of Mathematical Sciences, HBNI, 600113, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mahajan", 
            "givenName": "Meena", 
            "id": "sg:person.015704527337.23", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015704527337.23"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Chennai Mathematical Institute", 
              "id": "https://www.grid.ac/institutes/grid.444722.3", 
              "name": [
                "Chennai Mathematical Institute, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nimbhorkar", 
            "givenName": "Prajakta", 
            "id": "sg:person.015537550337.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015537550337.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Mathematical Sciences", 
              "id": "https://www.grid.ac/institutes/grid.462414.1", 
              "name": [
                "The Institute of Mathematical Sciences, HBNI, 600113, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tawari", 
            "givenName": "Anuj", 
            "id": "sg:person.011451161613.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011451161613.09"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00224-014-9574-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035612503", 
              "https://doi.org/10.1007/s00224-014-9574-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2016.03.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042159792"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-013-9747-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051356451", 
              "https://doi.org/10.1007/s00453-013-9747-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/qam/102435", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059346713"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0403021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062844612"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/16m1064738", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062874524"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.orl.2018.02.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1101129318"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-09-10", 
        "datePublishedReg": "2018-09-10", 
        "description": "We study bounded-depth (min,+) formulas computing the shortest path polynomial. For depth 2d with d\u22652, we obtain lower bounds parameterized by certain fan-in restrictions on + gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s12572-018-0229-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050051", 
            "issn": [
              "0975-0770", 
              "0975-5616"
            ], 
            "name": "International Journal of Advances in Engineering Sciences and Applied Mathematics", 
            "type": "Periodical"
          }
        ], 
        "name": "Shortest path length with bounded-alternation (min,+) formulas", 
        "pagination": "1-7", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "fc2e66e97a86d99a01530028aea9186743b9d909e0cd84583e48569c0a2598e0"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s12572-018-0229-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1106912865"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s12572-018-0229-6", 
          "https://app.dimensions.ai/details/publication/pub.1106912865"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:10", 
        "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_8678_00000517.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs12572-018-0229-6"
      }
    ]
     

    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/s12572-018-0229-6'

    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/s12572-018-0229-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-0229-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-0229-6'


     

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

    87 TRIPLES      20 PREDICATES      29 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s12572-018-0229-6 schema:author Nfbdcce001f064a8dbaa2423298de0bb9
    2 schema:citation sg:pub.10.1007/s00224-014-9574-4
    3 sg:pub.10.1007/s00453-013-9747-6
    4 https://doi.org/10.1016/j.orl.2018.02.003
    5 https://doi.org/10.1016/j.tcs.2016.03.014
    6 https://doi.org/10.1090/qam/102435
    7 https://doi.org/10.1137/0403021
    8 https://doi.org/10.1137/16m1064738
    9 schema:datePublished 2018-09-10
    10 schema:datePublishedReg 2018-09-10
    11 schema:description We study bounded-depth (min,+) formulas computing the shortest path polynomial. For depth 2d with d≥2, we obtain lower bounds parameterized by certain fan-in restrictions on + gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf sg:journal.1050051
    16 schema:name Shortest path length with bounded-alternation (min,+) formulas
    17 schema:pagination 1-7
    18 schema:productId N92795ed3c1c445c287f5441b7f31acb9
    19 N9a1a8e7b08ae4b74a8ac7e95b6e6302d
    20 Nbb143434639d44a19c9fdc1403a2c12e
    21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106912865
    22 https://doi.org/10.1007/s12572-018-0229-6
    23 schema:sdDatePublished 2019-04-10T19:10
    24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    25 schema:sdPublisher N3bbd3318f2d1453a836d38843a175d73
    26 schema:url http://link.springer.com/10.1007%2Fs12572-018-0229-6
    27 sgo:license sg:explorer/license/
    28 sgo:sdDataset articles
    29 rdf:type schema:ScholarlyArticle
    30 N3bbd3318f2d1453a836d38843a175d73 schema:name Springer Nature - SN SciGraph project
    31 rdf:type schema:Organization
    32 N5d24fd3e4f0b4d2da080fef99d301bbb rdf:first sg:person.011451161613.09
    33 rdf:rest rdf:nil
    34 N86c46a61510e443a91b281b828e8d524 rdf:first sg:person.015537550337.02
    35 rdf:rest N5d24fd3e4f0b4d2da080fef99d301bbb
    36 N92795ed3c1c445c287f5441b7f31acb9 schema:name doi
    37 schema:value 10.1007/s12572-018-0229-6
    38 rdf:type schema:PropertyValue
    39 N9a1a8e7b08ae4b74a8ac7e95b6e6302d schema:name dimensions_id
    40 schema:value pub.1106912865
    41 rdf:type schema:PropertyValue
    42 Nbb143434639d44a19c9fdc1403a2c12e schema:name readcube_id
    43 schema:value fc2e66e97a86d99a01530028aea9186743b9d909e0cd84583e48569c0a2598e0
    44 rdf:type schema:PropertyValue
    45 Nfbdcce001f064a8dbaa2423298de0bb9 rdf:first sg:person.015704527337.23
    46 rdf:rest N86c46a61510e443a91b281b828e8d524
    47 sg:journal.1050051 schema:issn 0975-0770
    48 0975-5616
    49 schema:name International Journal of Advances in Engineering Sciences and Applied Mathematics
    50 rdf:type schema:Periodical
    51 sg:person.011451161613.09 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
    52 schema:familyName Tawari
    53 schema:givenName Anuj
    54 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011451161613.09
    55 rdf:type schema:Person
    56 sg:person.015537550337.02 schema:affiliation https://www.grid.ac/institutes/grid.444722.3
    57 schema:familyName Nimbhorkar
    58 schema:givenName Prajakta
    59 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015537550337.02
    60 rdf:type schema:Person
    61 sg:person.015704527337.23 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
    62 schema:familyName Mahajan
    63 schema:givenName Meena
    64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015704527337.23
    65 rdf:type schema:Person
    66 sg:pub.10.1007/s00224-014-9574-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035612503
    67 https://doi.org/10.1007/s00224-014-9574-4
    68 rdf:type schema:CreativeWork
    69 sg:pub.10.1007/s00453-013-9747-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051356451
    70 https://doi.org/10.1007/s00453-013-9747-6
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1016/j.orl.2018.02.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101129318
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1016/j.tcs.2016.03.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042159792
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1090/qam/102435 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059346713
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1137/0403021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844612
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1137/16m1064738 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062874524
    81 rdf:type schema:CreativeWork
    82 https://www.grid.ac/institutes/grid.444722.3 schema:alternateName Chennai Mathematical Institute
    83 schema:name Chennai Mathematical Institute, Chennai, India
    84 rdf:type schema:Organization
    85 https://www.grid.ac/institutes/grid.462414.1 schema:alternateName Institute of Mathematical Sciences
    86 schema:name The Institute of Mathematical Sciences, HBNI, 600113, Chennai, India
    87 rdf:type schema:Organization
     




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


    ...