@prefix prodottidellaricerca: . @prefix istituto: . @prefix prodotto: . istituto:CDS003 prodottidellaricerca:prodotto prodotto:ID269872 . @prefix modulo: . modulo:ID2111 prodottidellaricerca:prodotto prodotto:ID269872 . @prefix pubblicazioni: . @prefix unitaDiPersonaleInterno: . unitaDiPersonaleInterno:MATRICOLA14375 pubblicazioni:autoreCNRDi prodotto:ID269872 . modulo:ID2108 prodottidellaricerca:prodotto prodotto:ID269872 . @prefix rdf: . @prefix retescientifica: . prodotto:ID269872 rdf:type retescientifica:ProdottoDellaRicerca , prodotto:TIPO1101 . @prefix rdfs: . prodotto:ID269872 rdfs:label "Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds (Articolo in rivista)"@en . @prefix xsd: . prodotto:ID269872 pubblicazioni:anno "2013-01-01T00:00:00+01:00"^^xsd:gYear ; pubblicazioni:doi "10.1007/978-3-642-39212-2_42"^^xsd:string . @prefix skos: . prodotto:ID269872 skos:altLabel "
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)
"^^rdf:HTML ; pubblicazioni:autori "Becchetti L; Bonifaci V; Dirnberger M; Karrenbauer A; Mehlhorn K"^^xsd:string ; pubblicazioni:paginaInizio "472"^^xsd:string ; pubblicazioni:paginaFine "483"^^xsd:string ; pubblicazioni:numeroVolume "7966"^^xsd:string . @prefix ns11: . prodotto:ID269872 pubblicazioni:rivista ns11:ID583862 ; pubblicazioni:pagineTotali "12"^^xsd:string ; skos:note "ISI Web of Science (WOS)"^^xsd:string , "Scopu"^^xsd:string ; pubblicazioni:affiliazioni "Sapienza University of Rome, Rome, Italy\nIstituto di Analisi dei Sistemi ed Informatica, CNR, Rome, Italy\nMax Planck Institute for Computer Science, Saarbruecken, Germany"^^xsd:string ; pubblicazioni:titolo "Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds"^^xsd:string ; prodottidellaricerca: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."@en . @prefix ns12: . prodotto:ID269872 pubblicazioni:editore ns12:ID11936 ; prodottidellaricerca:prodottoDi modulo:ID2108 , istituto:CDS003 , modulo:ID2111 ; pubblicazioni:autoreCNR unitaDiPersonaleInterno:MATRICOLA14375 . ns12:ID11936 pubblicazioni:editoreDi prodotto:ID269872 . ns11:ID583862 pubblicazioni:rivistaDi prodotto:ID269872 .