Minimum rank and zero forcing number for butterfly networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-04

AUTHORS

Daniela Ferrero, Cyriac Grigorious, Thomas Kalinowski, Joe Ryan, Sudeep Stephen

ABSTRACT

Zero forcing is a graph propagation process introduced in quantum physics and theoretical computer science, and closely related to the minimum rank problem. The minimum rank of a graph is the smallest possible rank over all matrices described by a given network. We use this relationship to determine the minimum rank and the zero forcing number of butterfly networks, concluding they present optimal properties in regards to both problems. More... »

PAGES

970-988

References to SciGraph publications

  • 2017-10. Note on power propagation time and lower bounds for the power domination number in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2008. On the Fast Searching Problem in ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-018-0335-1

    DOI

    http://dx.doi.org/10.1007/s10878-018-0335-1

    DIMENSIONS

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


    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/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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Texas State University\u2013San Marcos", 
              "id": "https://www.grid.ac/institutes/grid.264772.2", 
              "name": [
                "Department of Mathematics, Texas State University, San Marcos, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ferrero", 
            "givenName": "Daniela", 
            "id": "sg:person.015517773717.53", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015517773717.53"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "King's College London", 
              "id": "https://www.grid.ac/institutes/grid.13097.3c", 
              "name": [
                "School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia", 
                "Graduate School, Kings College London, London, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Grigorious", 
            "givenName": "Cyriac", 
            "id": "sg:person.010507176761.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010507176761.36"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of New England", 
              "id": "https://www.grid.ac/institutes/grid.1020.3", 
              "name": [
                "School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia", 
                "School of Science and Technology, University of New England, Armidale, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kalinowski", 
            "givenName": "Thomas", 
            "id": "sg:person.014075711653.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014075711653.84"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Newcastle Australia", 
              "id": "https://www.grid.ac/institutes/grid.266842.c", 
              "name": [
                "School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ryan", 
            "givenName": "Joe", 
            "id": "sg:person.014235535465.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014235535465.60"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Institute of Science Education and Research", 
              "id": "https://www.grid.ac/institutes/grid.419643.d", 
              "name": [
                "School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia", 
                "School of Mathematical Sciences, National Institute of Science Education and Research, Bhubaneswar, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Stephen", 
            "givenName": "Sudeep", 
            "id": "sg:person.016611624035.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016611624035.43"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.laa.2010.01.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000100655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.laa.2007.05.036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007874501"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-016-0103-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017894028", 
              "https://doi.org/10.1007/s10878-016-0103-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-016-0103-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017894028", 
              "https://doi.org/10.1007/s10878-016-0103-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1751-8113/41/48/482002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018549163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2013.04.015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019996751"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(96)00177-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029676660"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.99.100501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032081273"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.99.100501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032081273"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(91)90003-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033945460"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-68880-8_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039424194", 
              "https://doi.org/10.1007/978-3-540-68880-8_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2012.04.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039765230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/59.260810", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061192848"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480100375831", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882554"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.23919/acc.2004.1384521", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1104278364"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.23919/acc.2004.1384521", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1104278364"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-04", 
        "datePublishedReg": "2019-04-01", 
        "description": "Zero forcing is a graph propagation process introduced in quantum physics and theoretical computer science, and closely related to the minimum rank problem. The minimum rank of a graph is the smallest possible rank over all matrices described by a given network. We use this relationship to determine the minimum rank and the zero forcing number of butterfly networks, concluding they present optimal properties in regards to both problems.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10878-018-0335-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "37"
          }
        ], 
        "name": "Minimum rank and zero forcing number for butterfly networks", 
        "pagination": "970-988", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "67236aa05416a6b89a305fc0bb061704cddbac7d444b266cf182617a6dceb93b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-018-0335-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1106082396"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-018-0335-1", 
          "https://app.dimensions.ai/details/publication/pub.1106082396"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:05", 
        "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/0000000366_0000000366/records_112069_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs10878-018-0335-1"
      }
    ]
     

    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-018-0335-1'

    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-018-0335-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-018-0335-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-018-0335-1'


     

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

    148 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-018-0335-1 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nf0c791beeae94bd7a6aa4ecaa6ae3862
    4 schema:citation sg:pub.10.1007/978-3-540-68880-8_15
    5 sg:pub.10.1007/s10878-016-0103-z
    6 https://doi.org/10.1002/net.20095
    7 https://doi.org/10.1016/0196-6774(91)90003-h
    8 https://doi.org/10.1016/j.dam.2012.04.003
    9 https://doi.org/10.1016/j.laa.2007.05.036
    10 https://doi.org/10.1016/j.laa.2010.01.001
    11 https://doi.org/10.1016/j.tcs.2013.04.015
    12 https://doi.org/10.1016/s0304-3975(96)00177-6
    13 https://doi.org/10.1088/1751-8113/41/48/482002
    14 https://doi.org/10.1103/physrevlett.99.100501
    15 https://doi.org/10.1109/59.260810
    16 https://doi.org/10.1137/s0895480100375831
    17 https://doi.org/10.23919/acc.2004.1384521
    18 schema:datePublished 2019-04
    19 schema:datePublishedReg 2019-04-01
    20 schema:description Zero forcing is a graph propagation process introduced in quantum physics and theoretical computer science, and closely related to the minimum rank problem. The minimum rank of a graph is the smallest possible rank over all matrices described by a given network. We use this relationship to determine the minimum rank and the zero forcing number of butterfly networks, concluding they present optimal properties in regards to both problems.
    21 schema:genre research_article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree true
    24 schema:isPartOf N1965eaef67c04e82a4906a4ba56c61fc
    25 Nbafe64e1f19141a89b7e1295b88c891b
    26 sg:journal.1036683
    27 schema:name Minimum rank and zero forcing number for butterfly networks
    28 schema:pagination 970-988
    29 schema:productId N76004bff99a54acd9c62053d87a30d53
    30 N87f744fd70d24631aed296cfeb8751dd
    31 Nd08318cfebe942ebb9236e999e59a49e
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106082396
    33 https://doi.org/10.1007/s10878-018-0335-1
    34 schema:sdDatePublished 2019-04-11T13:05
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N3a658d97602046beb66af025e3020f71
    37 schema:url https://link.springer.com/10.1007%2Fs10878-018-0335-1
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset articles
    40 rdf:type schema:ScholarlyArticle
    41 N1965eaef67c04e82a4906a4ba56c61fc schema:volumeNumber 37
    42 rdf:type schema:PublicationVolume
    43 N34b1e5a0b4304a659f909df28591e5b7 rdf:first sg:person.010507176761.36
    44 rdf:rest N5c91969bf728491c8c8d6f348be5067a
    45 N3a658d97602046beb66af025e3020f71 schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N5c91969bf728491c8c8d6f348be5067a rdf:first sg:person.014075711653.84
    48 rdf:rest Nb7bf3838749f45b5bbde5a9c040098cc
    49 N76004bff99a54acd9c62053d87a30d53 schema:name doi
    50 schema:value 10.1007/s10878-018-0335-1
    51 rdf:type schema:PropertyValue
    52 N87f744fd70d24631aed296cfeb8751dd schema:name readcube_id
    53 schema:value 67236aa05416a6b89a305fc0bb061704cddbac7d444b266cf182617a6dceb93b
    54 rdf:type schema:PropertyValue
    55 Nb7bf3838749f45b5bbde5a9c040098cc rdf:first sg:person.014235535465.60
    56 rdf:rest Ncc157daccd0d49f68b0857496c04ba62
    57 Nbafe64e1f19141a89b7e1295b88c891b schema:issueNumber 3
    58 rdf:type schema:PublicationIssue
    59 Ncc157daccd0d49f68b0857496c04ba62 rdf:first sg:person.016611624035.43
    60 rdf:rest rdf:nil
    61 Nd08318cfebe942ebb9236e999e59a49e schema:name dimensions_id
    62 schema:value pub.1106082396
    63 rdf:type schema:PropertyValue
    64 Nf0c791beeae94bd7a6aa4ecaa6ae3862 rdf:first sg:person.015517773717.53
    65 rdf:rest N34b1e5a0b4304a659f909df28591e5b7
    66 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Mathematical Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Pure Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1036683 schema:issn 1382-6905
    73 1573-2886
    74 schema:name Journal of Combinatorial Optimization
    75 rdf:type schema:Periodical
    76 sg:person.010507176761.36 schema:affiliation https://www.grid.ac/institutes/grid.13097.3c
    77 schema:familyName Grigorious
    78 schema:givenName Cyriac
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010507176761.36
    80 rdf:type schema:Person
    81 sg:person.014075711653.84 schema:affiliation https://www.grid.ac/institutes/grid.1020.3
    82 schema:familyName Kalinowski
    83 schema:givenName Thomas
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014075711653.84
    85 rdf:type schema:Person
    86 sg:person.014235535465.60 schema:affiliation https://www.grid.ac/institutes/grid.266842.c
    87 schema:familyName Ryan
    88 schema:givenName Joe
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014235535465.60
    90 rdf:type schema:Person
    91 sg:person.015517773717.53 schema:affiliation https://www.grid.ac/institutes/grid.264772.2
    92 schema:familyName Ferrero
    93 schema:givenName Daniela
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015517773717.53
    95 rdf:type schema:Person
    96 sg:person.016611624035.43 schema:affiliation https://www.grid.ac/institutes/grid.419643.d
    97 schema:familyName Stephen
    98 schema:givenName Sudeep
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016611624035.43
    100 rdf:type schema:Person
    101 sg:pub.10.1007/978-3-540-68880-8_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039424194
    102 https://doi.org/10.1007/978-3-540-68880-8_15
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/s10878-016-0103-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1017894028
    105 https://doi.org/10.1007/s10878-016-0103-z
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1002/net.20095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015469195
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/0196-6774(91)90003-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1033945460
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/j.dam.2012.04.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039765230
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/j.laa.2007.05.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007874501
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/j.laa.2010.01.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000100655
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/j.tcs.2013.04.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019996751
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/s0304-3975(96)00177-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029676660
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1088/1751-8113/41/48/482002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018549163
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1103/physrevlett.99.100501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032081273
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1109/59.260810 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061192848
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1137/s0895480100375831 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882554
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.23919/acc.2004.1384521 schema:sameAs https://app.dimensions.ai/details/publication/pub.1104278364
    130 rdf:type schema:CreativeWork
    131 https://www.grid.ac/institutes/grid.1020.3 schema:alternateName University of New England
    132 schema:name School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia
    133 School of Science and Technology, University of New England, Armidale, Australia
    134 rdf:type schema:Organization
    135 https://www.grid.ac/institutes/grid.13097.3c schema:alternateName King's College London
    136 schema:name Graduate School, Kings College London, London, UK
    137 School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia
    138 rdf:type schema:Organization
    139 https://www.grid.ac/institutes/grid.264772.2 schema:alternateName Texas State University–San Marcos
    140 schema:name Department of Mathematics, Texas State University, San Marcos, USA
    141 rdf:type schema:Organization
    142 https://www.grid.ac/institutes/grid.266842.c schema:alternateName University of Newcastle Australia
    143 schema:name School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia
    144 rdf:type schema:Organization
    145 https://www.grid.ac/institutes/grid.419643.d schema:alternateName National Institute of Science Education and Research
    146 schema:name School of Mathematical Sciences, National Institute of Science Education and Research, Bhubaneswar, India
    147 School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, Australia
    148 rdf:type schema:Organization
     




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


    ...