@prefix pubblicazioni: . @prefix unitaDiPersonaleInterno: . @prefix prodotto: . unitaDiPersonaleInterno:MATRICOLA7567 pubblicazioni:autoreCNRDi prodotto:ID170809 . @prefix prodottidellaricerca: . @prefix istituto: . istituto:CDS003 prodottidellaricerca:prodotto prodotto:ID170809 . @prefix unitaDiPersonaleEsterno: . unitaDiPersonaleEsterno:ID6164 pubblicazioni:autoreCNRDi prodotto:ID170809 . @prefix modulo: . modulo:ID2271 prodottidellaricerca:prodotto prodotto:ID170809 . @prefix rdf: . prodotto:ID170809 rdf:type prodotto:TIPO1101 . @prefix retescientifica: . prodotto:ID170809 rdf:type retescientifica:ProdottoDellaRicerca . @prefix rdfs: . prodotto:ID170809 rdfs:label "Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs (Articolo in rivista)"@en . @prefix xsd: . prodotto:ID170809 pubblicazioni:anno "2003-01-01T00:00:00+01:00"^^xsd:gYear . @prefix skos: . prodotto:ID170809 skos:altLabel "
Gaibisso, C.; Proietti, G.; Tan, R. B. Gaibisso, C.; Proietti, G.; Tan, R. (2003)
Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
in Lecture notes in computer science
"^^rdf:HTML ; pubblicazioni:autori "Gaibisso, C.; Proietti, G.; Tan, R. B. Gaibisso, C.; Proietti, G.; Tan, R."^^xsd:string ; pubblicazioni:paginaInizio "404"^^xsd:string ; pubblicazioni:paginaFine "414"^^xsd:string ; pubblicazioni:numeroVolume "2697"^^xsd:string . @prefix ns12: . prodotto:ID170809 pubblicazioni:rivista ns12:ID583862 ; pubblicazioni:note "Vol.2697; series: Lecture Notes in Computer Science; pp.404-414.\nTech. Rep. 586, IASI-CNR"^^xsd:string ; skos:note "ISI Web of Science (WOS)"^^xsd:string ; pubblicazioni:titolo "Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs"^^xsd:string ; prodottidellaricerca:abstract "Given a minimum spanning tree of a 2-node connected, real\nweighted, planar graph $G=(V,E)$ with $n$ nodes, we study the\nproblem of finding, for every node $v \\in V$, a minimum spanning\ntree of the graph $G-v$ (the graph $G$ deprived of $v$ and all its\nincident edges). We show that this problem can be solved on a\npointer machine in optimal linear time, thus improving the\nprevious known ${\\cal O}(n \\cdot\\alpha(n,n))$ time bound holding\nfor general sparse graphs, where $\\alpha$ is the functional\ninverse of Ackermann's function. In this way, we obtain the same\nruntime as for the edge removal version of the problem, thus\nfilling the previously existing gap. Our algorithm finds\napplication in maintaining wireless networks undergoing transient\nstation failures." ; prodottidellaricerca:prodottoDi istituto:CDS003 , modulo:ID2271 ; pubblicazioni:autoreCNR unitaDiPersonaleEsterno:ID6164 , unitaDiPersonaleInterno:MATRICOLA7567 . ns12:ID583862 pubblicazioni:rivistaDi prodotto:ID170809 .