Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds (Articolo in rivista)

Type
Label
  • Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds (Articolo in rivista) (literal)
Anno
  • 2013-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/978-3-642-39212-2_42 (literal)
Alternative label
  • Becchetti L; Bonifaci V; Dirnberger M; Karrenbauer A; Mehlhorn K (2013)
    Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
    in Lecture notes in computer science; Springer, Berlin (Germania)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Becchetti L; Bonifaci V; Dirnberger M; Karrenbauer A; Mehlhorn K (literal)
Pagina inizio
  • 472 (literal)
Pagina fine
  • 483 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 7966 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 12 (literal)
Note
  • ISI Web of Science (WOS) (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Sapienza University of Rome, Rome, Italy Istituto di Analisi dei Sistemi ed Informatica, CNR, Rome, Italy Max Planck Institute for Computer Science, Saarbruecken, Germany (literal)
Titolo
  • Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds (literal)
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 + eps)-approximation of the shortest path in O( m L (logn + log L)/eps^3) iterations, with arithmetic on numbers of O(log(nL/eps)) 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. (2011): convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case. (literal)
Editore
Prodotto di
Autore CNR

Incoming links:


Prodotto
Autore CNR di
Editore di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it