Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Luca Becchetti , Vincenzo Bonifaci , Michael Dirnberger , Andreas Karrenbauer , Kurt Mehlhorn

ABSTRACT

Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime’s behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + ε)-approximation of the shortest path in O( mL (logn + logL)/ε3) iterations, with arithmetic on numbers of O(log(nL/ε)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case. More... »

PAGES

472-483

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_42

DOI

http://dx.doi.org/10.1007/978-3-642-39212-2_42

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dipartimento di Informatica e Sistemistica, Sapienza Universit\u00e0 di Roma, Italy", 
          "id": "http://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Sapienza Universit\u00e0 di Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Becchetti", 
        "givenName": "Luca", 
        "id": "sg:person.011301474260.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011301474260.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Istituto di Analisi dei Sistemi ed Informatica \u201cAntonio Ruberti\u201d, Consiglio Nazionale delle Ricerche, Rome, Italy", 
          "id": "http://www.grid.ac/institutes/grid.419461.f", 
          "name": [
            "Istituto di Analisi dei Sistemi ed Informatica \u201cAntonio Ruberti\u201d, Consiglio Nazionale delle Ricerche, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonifaci", 
        "givenName": "Vincenzo", 
        "id": "sg:person.013326621163.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013326621163.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dirnberger", 
        "givenName": "Michael", 
        "id": "sg:person.014500756033.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014500756033.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karrenbauer", 
        "givenName": "Andreas", 
        "id": "sg:person.01170462124.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01170462124.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime\u2019s behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1\u2009+\u2009\u03b5)-approximation of the shortest path in O( mL (logn\u2009+\u2009logL)/\u03b53) iterations, with arithmetic on numbers of O(log(nL/\u03b5)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39212-2_42", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39211-5", 
        "978-3-642-39212-2"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "complexity bounds", 
      "shortest path problem", 
      "differential equations", 
      "shortest path", 
      "O( n log2 n) iterations", 
      "mathematical model", 
      "convergence proof", 
      "Physarum model", 
      "path problem", 
      "number of nodes", 
      "discretization", 
      "uniform case", 
      "nonuniform case", 
      "bounds", 
      "convergence", 
      "large length", 
      "Ito et al", 
      "equations", 
      "approximation", 
      "iteration", 
      "et al", 
      "model", 
      "graph", 
      "edge", 
      "Nakagaki", 
      "path", 
      "problem", 
      "proof", 
      "Kobayashi", 
      "tero", 
      "number", 
      "cases", 
      "behavior", 
      "system", 
      "nodes", 
      "Physarum", 
      "al", 
      "Physarum polycephalum", 
      "bits", 
      "form", 
      "slime mold", 
      "results", 
      "length", 
      "polycephalum", 
      "mold"
    ], 
    "name": "Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds", 
    "pagination": "472-483", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005927901"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39212-2_42"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39212-2_42", 
      "https://app.dimensions.ai/details/publication/pub.1005927901"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_74.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-39212-2_42"
  }
]
 

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/978-3-642-39212-2_42'

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/978-3-642-39212-2_42'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_42'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_42'


 

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

153 TRIPLES      22 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39212-2_42 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N4e0bf41bf5784582a0ced40e909c0aba
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime’s behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + ε)-approximation of the shortest path in O( mL (logn + logL)/ε3) iterations, with arithmetic on numbers of O(log(nL/ε)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case.
7 schema:editor N5bb995049d7346b59c32f0325b598126
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N98094cd32cc54aaaa839188a21d56edf
11 schema:keywords Ito et al
12 Kobayashi
13 Nakagaki
14 O( n log2 n) iterations
15 Physarum
16 Physarum model
17 Physarum polycephalum
18 al
19 approximation
20 behavior
21 bits
22 bounds
23 cases
24 complexity bounds
25 convergence
26 convergence proof
27 differential equations
28 discretization
29 edge
30 equations
31 et al
32 form
33 graph
34 iteration
35 large length
36 length
37 mathematical model
38 model
39 mold
40 nodes
41 nonuniform case
42 number
43 number of nodes
44 path
45 path problem
46 polycephalum
47 problem
48 proof
49 results
50 shortest path
51 shortest path problem
52 slime mold
53 system
54 tero
55 uniform case
56 schema:name Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
57 schema:pagination 472-483
58 schema:productId Ndef745edd1964daf81ed0f19b60dd832
59 Nec62b54467dd4fa09edbc4fe2ab58bcf
60 schema:publisher N5d5f7ead84d544fea3085f98da3a2832
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005927901
62 https://doi.org/10.1007/978-3-642-39212-2_42
63 schema:sdDatePublished 2022-09-02T16:17
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Naa73878d6351482f945ee3d8ea016e22
66 schema:url https://doi.org/10.1007/978-3-642-39212-2_42
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N1603f9d992f84cc483b5c4bdd194b2ec rdf:first sg:person.011757371347.43
71 rdf:rest rdf:nil
72 N31836b7fd0b14f49b1ceac97f031bcd3 rdf:first sg:person.01170462124.60
73 rdf:rest N1603f9d992f84cc483b5c4bdd194b2ec
74 N4e0bf41bf5784582a0ced40e909c0aba rdf:first sg:person.011301474260.17
75 rdf:rest Nac9a63c7d6b54b65bccdaf246f6c0050
76 N5bb995049d7346b59c32f0325b598126 rdf:first N5d87722ae5aa47d0816b2e32c100addc
77 rdf:rest Nc1edd78c90214b738104d76d13702a23
78 N5d5f7ead84d544fea3085f98da3a2832 schema:name Springer Nature
79 rdf:type schema:Organisation
80 N5d87722ae5aa47d0816b2e32c100addc schema:familyName Fomin
81 schema:givenName Fedor V.
82 rdf:type schema:Person
83 N6f4e7e0001b34bcab5a544b05f9c45ea rdf:first Neb46d0503022461597873c27d882f42c
84 rdf:rest N96d088f228fe4c038e152e5334cf971b
85 N88c6f6eea95045b782889c792fbbc809 schema:familyName Freivalds
86 schema:givenName Rūsiņš
87 rdf:type schema:Person
88 N92cd352327744e4bba3d312e98a6828b schema:familyName Peleg
89 schema:givenName David
90 rdf:type schema:Person
91 N96d088f228fe4c038e152e5334cf971b rdf:first N92cd352327744e4bba3d312e98a6828b
92 rdf:rest rdf:nil
93 N98094cd32cc54aaaa839188a21d56edf schema:isbn 978-3-642-39211-5
94 978-3-642-39212-2
95 schema:name Automata, Languages, and Programming
96 rdf:type schema:Book
97 Naa73878d6351482f945ee3d8ea016e22 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Nac9a63c7d6b54b65bccdaf246f6c0050 rdf:first sg:person.013326621163.01
100 rdf:rest Nad48f1573df24f4cbc152d0a3e02b168
101 Nad48f1573df24f4cbc152d0a3e02b168 rdf:first sg:person.014500756033.31
102 rdf:rest N31836b7fd0b14f49b1ceac97f031bcd3
103 Nc1edd78c90214b738104d76d13702a23 rdf:first N88c6f6eea95045b782889c792fbbc809
104 rdf:rest N6f4e7e0001b34bcab5a544b05f9c45ea
105 Ndef745edd1964daf81ed0f19b60dd832 schema:name doi
106 schema:value 10.1007/978-3-642-39212-2_42
107 rdf:type schema:PropertyValue
108 Neb46d0503022461597873c27d882f42c schema:familyName Kwiatkowska
109 schema:givenName Marta
110 rdf:type schema:Person
111 Nec62b54467dd4fa09edbc4fe2ab58bcf schema:name dimensions_id
112 schema:value pub.1005927901
113 rdf:type schema:PropertyValue
114 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
115 schema:name Mathematical Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
118 schema:name Pure Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.011301474260.17 schema:affiliation grid-institutes:grid.7841.a
121 schema:familyName Becchetti
122 schema:givenName Luca
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011301474260.17
124 rdf:type schema:Person
125 sg:person.01170462124.60 schema:affiliation grid-institutes:grid.419528.3
126 schema:familyName Karrenbauer
127 schema:givenName Andreas
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01170462124.60
129 rdf:type schema:Person
130 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
131 schema:familyName Mehlhorn
132 schema:givenName Kurt
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
134 rdf:type schema:Person
135 sg:person.013326621163.01 schema:affiliation grid-institutes:grid.419461.f
136 schema:familyName Bonifaci
137 schema:givenName Vincenzo
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013326621163.01
139 rdf:type schema:Person
140 sg:person.014500756033.31 schema:affiliation grid-institutes:grid.419528.3
141 schema:familyName Dirnberger
142 schema:givenName Michael
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014500756033.31
144 rdf:type schema:Person
145 grid-institutes:grid.419461.f schema:alternateName Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, Consiglio Nazionale delle Ricerche, Rome, Italy
146 schema:name Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, Consiglio Nazionale delle Ricerche, Rome, Italy
147 rdf:type schema:Organization
148 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarbrücken, Germany
149 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
150 rdf:type schema:Organization
151 grid-institutes:grid.7841.a schema:alternateName Dipartimento di Informatica e Sistemistica, Sapienza Università di Roma, Italy
152 schema:name Dipartimento di Informatica e Sistemistica, Sapienza Università di Roma, Italy
153 rdf:type schema:Organization
 




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


...