Depletable channels: dynamics, behaviour, and efficiency in network design View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-11-08

AUTHORS

Pietro Cenciarelli, Daniele Gorla, Ivano Salvo

ABSTRACT

We present a simple model, called depleatable channels, of multi-hop communication in ad hoc networks. We introduce a model for channel energy consumption, and we propose a notion of channel equivalence based on the communication service they provide, regardless of specific routing protocols. In particular, we consider equivalent two channels with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence, and variants of it, coincide with standard equivalences borrowed from the theory of concurrency. Unfortunately, while the maximum flow can be computed in polynomial time, calculating the value of a minimum inhibiting flow is NP-hard. Thus, we propose a characterization of those graphs, called weak, which admit charge assignments for which the minimum inhibiting flow is strictly less than the maximum flow and show that weakness can be checked efficiently by providing an algorithm that does so in polynomial time. More... »

PAGES

1-27

References to SciGraph publications

  • 2013. Modelling MAC-Layer Communications in Wireless Systems in COORDINATION MODELS AND LANGUAGES
  • 2012. Modelling Probabilistic Wireless Networks in FORMAL TECHNIQUES FOR DISTRIBUTED SYSTEMS
  • 1968-12. Über ein Paradoxon aus der Verkehrsplanung in NONE
  • 2018. Ad Hoc Networks in NONE
  • 2014. Characterising Testing Preorders for Broadcasting Distributed Systems in TRUSTWORTHY GLOBAL COMPUTING
  • 2008. Network Applications of Graph Bisimulation in GRAPH TRANSFORMATIONS
  • 2009. Depletable Channels: Dynamics and Behaviour in FUNDAMENTALS OF COMPUTATION THEORY
  • 2016-08. Modelling and verifying the AODV routing protocol in DISTRIBUTED COMPUTING
  • 2013-09. A calculus of trustworthy ad hoc networks in FORMAL ASPECTS OF COMPUTING
  • 1993. The linear time — Branching time spectrum II in CONCUR'93
  • 2011. Semantic Analysis of Gossip Protocols for Wireless Sensor Networks in CONCUR 2011 – CONCURRENCY THEORY
  • 1981. Concurrency and automata on infinite sequences in THEORETICAL COMPUTER SCIENCE
  • 2019-04. A Polynomial-Time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs in ALGORITHMICA
  • 1972-05. Schnittverbände in Graphen in ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITÄT HAMBURG
  • 2016-11. Network Characterizations for Excluding Braess’s Paradox in THEORY OF COMPUTING SYSTEMS
  • 2016-03. Mechanizing a Process Algebra for Network Protocols in JOURNAL OF AUTOMATED REASONING
  • 2015. Excluding Braess’s Paradox in Nonatomic Selfish Routing in ALGORITHMIC GAME THEORY
  • Journal

    TITLE

    Acta Informatica

    ISSUE

    N/A

    VOLUME

    N/A

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-018-0329-6

    DOI

    http://dx.doi.org/10.1007/s00236-018-0329-6

    DIMENSIONS

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


    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/1005", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Communications Technologies", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Technology", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, Sapienza University of Rome, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cenciarelli", 
            "givenName": "Pietro", 
            "id": "sg:person.015012206477.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015012206477.74"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, Sapienza University of Rome, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gorla", 
            "givenName": "Daniele", 
            "id": "sg:person.014525127615.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014525127615.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, Sapienza University of Rome, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Salvo", 
            "givenName": "Ivano", 
            "id": "sg:person.010477456677.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010477456677.24"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.jcss.2005.05.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002226501"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-48433-3_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005019905", 
              "https://doi.org/10.1007/978-3-662-48433-3_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0898-1221(98)00077-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005702935"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-23217-6_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006488903", 
              "https://doi.org/10.1007/978-3-642-23217-6_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-23217-6_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006488903", 
              "https://doi.org/10.1007/978-3-642-23217-6_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.scico.2013.01.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009603891"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00165-011-0210-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010205311", 
              "https://doi.org/10.1007/s00165-011-0210-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0017309", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013247095", 
              "https://doi.org/10.1007/bfb0017309"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2010.01.023", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014133885"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57208-2_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014426033", 
              "https://doi.org/10.1007/3-540-57208-2_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.scico.2009.07.008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015432679"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/167088.167286", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015862754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2011.03.017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020079320"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/b978-044482830-9/50021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024585805"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90025-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024801031"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-015-9358-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024968079", 
              "https://doi.org/10.1007/s10817-015-9358-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.geb.2005.09.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025514698"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-45917-1_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026620116", 
              "https://doi.org/10.1007/978-3-662-45917-1_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2011.07.016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027951027"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01918335", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028360600", 
              "https://doi.org/10.1007/bf01918335"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2006.08.036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028743769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02996932", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030284848", 
              "https://doi.org/10.1007/bf02996932"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38493-6_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030791883", 
              "https://doi.org/10.1007/978-3-642-38493-6_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03409-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032004644", 
              "https://doi.org/10.1007/978-3-642-03409-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2007.11.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035348497"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.adhoc.2003.09.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035647585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(97)83809-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037058919"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-87405-8_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037652135", 
              "https://doi.org/10.1007/978-3-540-87405-8_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-87405-8_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037652135", 
              "https://doi.org/10.1007/978-3-540-87405-8_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-30793-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038238673", 
              "https://doi.org/10.1007/978-3-642-30793-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-016-9710-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040537902", 
              "https://doi.org/10.1007/s00224-016-9710-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-016-9710-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040537902", 
              "https://doi.org/10.1007/s00224-016-9710-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(84)90113-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043830842"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.entcs.2006.04.017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045476157"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-015-0262-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049851660", 
              "https://doi.org/10.1007/s00446-015-0262-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/mcom.2002.1024422", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061393425"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753979427087x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879954"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2168/lmcs-11(1:18)2015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069150752"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2168/lmcs-9(3:26)2013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069151302"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cjm-1956-045-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072264069"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2017.10.008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093123366"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infocom.2015.7218419", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094372914"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icis.2007.161", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095207048"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/vtcspring.2015.7145650", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095554705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/dcoss.2014.9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095686577"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1103153083", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-981-10-8770-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1103153083", 
              "https://doi.org/10.1007/978-981-10-8770-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-018-0486-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105776920", 
              "https://doi.org/10.1007/s00453-018-0486-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-018-0486-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105776920", 
              "https://doi.org/10.1007/s00453-018-0486-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1109698723", 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1109698723", 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/0470091126", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109698723"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-11-08", 
        "datePublishedReg": "2018-11-08", 
        "description": "We present a simple model, called depleatable channels, of multi-hop communication in ad hoc networks. We introduce a model for channel energy consumption, and we propose a notion of channel equivalence based on the communication service they provide, regardless of specific routing protocols. In particular, we consider equivalent two channels with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence, and variants of it, coincide with standard equivalences borrowed from the theory of concurrency. Unfortunately, while the maximum flow can be computed in polynomial time, calculating the value of a minimum inhibiting flow is NP-hard. Thus, we propose a characterization of those graphs, called weak, which admit charge assignments for which the minimum inhibiting flow is strictly less than the maximum flow and show that weakness can be checked efficiently by providing an algorithm that does so in polynomial time.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00236-018-0329-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "type": "Periodical"
          }
        ], 
        "name": "Depletable channels: dynamics, behaviour, and efficiency in network design", 
        "pagination": "1-27", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d782c9e188a0469a89460dae0a133a70321b8638ba4e2ee76088f5802905779d"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-018-0329-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1109785205"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-018-0329-6", 
          "https://app.dimensions.ai/details/publication/pub.1109785205"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T21:00", 
        "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_8684_00000610.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00236-018-0329-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/s00236-018-0329-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/s00236-018-0329-6'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    225 TRIPLES      21 PREDICATES      71 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-018-0329-6 schema:about anzsrc-for:10
    2 anzsrc-for:1005
    3 schema:author Nc19ddabf635f440bb4ea9ef174e1bafc
    4 schema:citation sg:pub.10.1007/3-540-57208-2_6
    5 sg:pub.10.1007/978-3-540-87405-8_10
    6 sg:pub.10.1007/978-3-642-03409-1_6
    7 sg:pub.10.1007/978-3-642-23217-6_11
    8 sg:pub.10.1007/978-3-642-30793-5_9
    9 sg:pub.10.1007/978-3-642-38493-6_2
    10 sg:pub.10.1007/978-3-662-45917-1_5
    11 sg:pub.10.1007/978-3-662-48433-3_17
    12 sg:pub.10.1007/978-981-10-8770-7
    13 sg:pub.10.1007/bf01918335
    14 sg:pub.10.1007/bf02996932
    15 sg:pub.10.1007/bfb0017309
    16 sg:pub.10.1007/s00165-011-0210-7
    17 sg:pub.10.1007/s00224-016-9710-4
    18 sg:pub.10.1007/s00446-015-0262-7
    19 sg:pub.10.1007/s00453-018-0486-6
    20 sg:pub.10.1007/s10817-015-9358-9
    21 https://app.dimensions.ai/details/publication/pub.1103153083
    22 https://app.dimensions.ai/details/publication/pub.1109698723
    23 https://doi.org/10.1002/0470091126
    24 https://doi.org/10.1016/0304-3975(84)90113-0
    25 https://doi.org/10.1016/0890-5401(90)90025-d
    26 https://doi.org/10.1016/b978-044482830-9/50021-7
    27 https://doi.org/10.1016/j.adhoc.2003.09.010
    28 https://doi.org/10.1016/j.entcs.2006.04.017
    29 https://doi.org/10.1016/j.geb.2005.09.005
    30 https://doi.org/10.1016/j.ic.2007.11.010
    31 https://doi.org/10.1016/j.ipl.2017.10.008
    32 https://doi.org/10.1016/j.jcss.2005.05.009
    33 https://doi.org/10.1016/j.scico.2009.07.008
    34 https://doi.org/10.1016/j.scico.2013.01.005
    35 https://doi.org/10.1016/j.tcs.2006.08.036
    36 https://doi.org/10.1016/j.tcs.2010.01.023
    37 https://doi.org/10.1016/j.tcs.2011.03.017
    38 https://doi.org/10.1016/j.tcs.2011.07.016
    39 https://doi.org/10.1016/s0304-3975(97)83809-1
    40 https://doi.org/10.1016/s0898-1221(98)00077-7
    41 https://doi.org/10.1109/dcoss.2014.9
    42 https://doi.org/10.1109/icis.2007.161
    43 https://doi.org/10.1109/infocom.2015.7218419
    44 https://doi.org/10.1109/mcom.2002.1024422
    45 https://doi.org/10.1109/vtcspring.2015.7145650
    46 https://doi.org/10.1137/s009753979427087x
    47 https://doi.org/10.1145/167088.167286
    48 https://doi.org/10.2168/lmcs-11(1:18)2015
    49 https://doi.org/10.2168/lmcs-9(3:26)2013
    50 https://doi.org/10.4153/cjm-1956-045-5
    51 schema:datePublished 2018-11-08
    52 schema:datePublishedReg 2018-11-08
    53 schema:description We present a simple model, called depleatable channels, of multi-hop communication in ad hoc networks. We introduce a model for channel energy consumption, and we propose a notion of channel equivalence based on the communication service they provide, regardless of specific routing protocols. In particular, we consider equivalent two channels with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence, and variants of it, coincide with standard equivalences borrowed from the theory of concurrency. Unfortunately, while the maximum flow can be computed in polynomial time, calculating the value of a minimum inhibiting flow is NP-hard. Thus, we propose a characterization of those graphs, called weak, which admit charge assignments for which the minimum inhibiting flow is strictly less than the maximum flow and show that weakness can be checked efficiently by providing an algorithm that does so in polynomial time.
    54 schema:genre research_article
    55 schema:inLanguage en
    56 schema:isAccessibleForFree false
    57 schema:isPartOf sg:journal.1133515
    58 schema:name Depletable channels: dynamics, behaviour, and efficiency in network design
    59 schema:pagination 1-27
    60 schema:productId N99cc80b955634927a2efca113dbeb43f
    61 Na41ca050508b44b78b21121b8efa2866
    62 Nc34be3f5fa124d38a3fceacc4ffbe516
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109785205
    64 https://doi.org/10.1007/s00236-018-0329-6
    65 schema:sdDatePublished 2019-04-10T21:00
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher Nb9dfc07a325040e3849a4415b77113c5
    68 schema:url https://link.springer.com/10.1007%2Fs00236-018-0329-6
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N71f3ec5d2f21426d90c9e21305b747d3 rdf:first sg:person.014525127615.31
    73 rdf:rest Nd7ccd3e5cc7340f9a16b4cf47afc41bf
    74 N99cc80b955634927a2efca113dbeb43f schema:name dimensions_id
    75 schema:value pub.1109785205
    76 rdf:type schema:PropertyValue
    77 Na41ca050508b44b78b21121b8efa2866 schema:name readcube_id
    78 schema:value d782c9e188a0469a89460dae0a133a70321b8638ba4e2ee76088f5802905779d
    79 rdf:type schema:PropertyValue
    80 Nb9dfc07a325040e3849a4415b77113c5 schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 Nc19ddabf635f440bb4ea9ef174e1bafc rdf:first sg:person.015012206477.74
    83 rdf:rest N71f3ec5d2f21426d90c9e21305b747d3
    84 Nc34be3f5fa124d38a3fceacc4ffbe516 schema:name doi
    85 schema:value 10.1007/s00236-018-0329-6
    86 rdf:type schema:PropertyValue
    87 Nd7ccd3e5cc7340f9a16b4cf47afc41bf rdf:first sg:person.010477456677.24
    88 rdf:rest rdf:nil
    89 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Technology
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Communications Technologies
    94 rdf:type schema:DefinedTerm
    95 sg:journal.1133515 schema:issn 0001-5903
    96 1432-0525
    97 schema:name Acta Informatica
    98 rdf:type schema:Periodical
    99 sg:person.010477456677.24 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    100 schema:familyName Salvo
    101 schema:givenName Ivano
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010477456677.24
    103 rdf:type schema:Person
    104 sg:person.014525127615.31 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    105 schema:familyName Gorla
    106 schema:givenName Daniele
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014525127615.31
    108 rdf:type schema:Person
    109 sg:person.015012206477.74 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    110 schema:familyName Cenciarelli
    111 schema:givenName Pietro
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015012206477.74
    113 rdf:type schema:Person
    114 sg:pub.10.1007/3-540-57208-2_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014426033
    115 https://doi.org/10.1007/3-540-57208-2_6
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-540-87405-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037652135
    118 https://doi.org/10.1007/978-3-540-87405-8_10
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-642-03409-1_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032004644
    121 https://doi.org/10.1007/978-3-642-03409-1_6
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-642-23217-6_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006488903
    124 https://doi.org/10.1007/978-3-642-23217-6_11
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-642-30793-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038238673
    127 https://doi.org/10.1007/978-3-642-30793-5_9
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-642-38493-6_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791883
    130 https://doi.org/10.1007/978-3-642-38493-6_2
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-662-45917-1_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026620116
    133 https://doi.org/10.1007/978-3-662-45917-1_5
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/978-3-662-48433-3_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005019905
    136 https://doi.org/10.1007/978-3-662-48433-3_17
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/978-981-10-8770-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103153083
    139 https://doi.org/10.1007/978-981-10-8770-7
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/bf01918335 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028360600
    142 https://doi.org/10.1007/bf01918335
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/bf02996932 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030284848
    145 https://doi.org/10.1007/bf02996932
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/bfb0017309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013247095
    148 https://doi.org/10.1007/bfb0017309
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/s00165-011-0210-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010205311
    151 https://doi.org/10.1007/s00165-011-0210-7
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1007/s00224-016-9710-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040537902
    154 https://doi.org/10.1007/s00224-016-9710-4
    155 rdf:type schema:CreativeWork
    156 sg:pub.10.1007/s00446-015-0262-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049851660
    157 https://doi.org/10.1007/s00446-015-0262-7
    158 rdf:type schema:CreativeWork
    159 sg:pub.10.1007/s00453-018-0486-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105776920
    160 https://doi.org/10.1007/s00453-018-0486-6
    161 rdf:type schema:CreativeWork
    162 sg:pub.10.1007/s10817-015-9358-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024968079
    163 https://doi.org/10.1007/s10817-015-9358-9
    164 rdf:type schema:CreativeWork
    165 https://app.dimensions.ai/details/publication/pub.1103153083 schema:CreativeWork
    166 https://app.dimensions.ai/details/publication/pub.1109698723 schema:CreativeWork
    167 https://doi.org/10.1002/0470091126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109698723
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/0304-3975(84)90113-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043830842
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/0890-5401(90)90025-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1024801031
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/b978-044482830-9/50021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024585805
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1016/j.adhoc.2003.09.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035647585
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1016/j.entcs.2006.04.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045476157
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1016/j.geb.2005.09.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025514698
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1016/j.ic.2007.11.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035348497
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1016/j.ipl.2017.10.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093123366
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1016/j.jcss.2005.05.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002226501
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1016/j.scico.2009.07.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015432679
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1016/j.scico.2013.01.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009603891
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1016/j.tcs.2006.08.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028743769
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1016/j.tcs.2010.01.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014133885
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1016/j.tcs.2011.03.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020079320
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1016/j.tcs.2011.07.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027951027
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1016/s0304-3975(97)83809-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037058919
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1016/s0898-1221(98)00077-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005702935
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1109/dcoss.2014.9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095686577
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1109/icis.2007.161 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095207048
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1109/infocom.2015.7218419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094372914
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1109/mcom.2002.1024422 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061393425
    210 rdf:type schema:CreativeWork
    211 https://doi.org/10.1109/vtcspring.2015.7145650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095554705
    212 rdf:type schema:CreativeWork
    213 https://doi.org/10.1137/s009753979427087x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879954
    214 rdf:type schema:CreativeWork
    215 https://doi.org/10.1145/167088.167286 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015862754
    216 rdf:type schema:CreativeWork
    217 https://doi.org/10.2168/lmcs-11(1:18)2015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069150752
    218 rdf:type schema:CreativeWork
    219 https://doi.org/10.2168/lmcs-9(3:26)2013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069151302
    220 rdf:type schema:CreativeWork
    221 https://doi.org/10.4153/cjm-1956-045-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264069
    222 rdf:type schema:CreativeWork
    223 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    224 schema:name Department of Computer Science, Sapienza University of Rome, Rome, Italy
    225 rdf:type schema:Organization
     




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


    ...