@prefix prodottidellaricerca: . @prefix istituto: . @prefix prodotto: . istituto:CDS003 prodottidellaricerca:prodotto prodotto:ID168050 . @prefix pubblicazioni: . @prefix unitaDiPersonaleInterno: . unitaDiPersonaleInterno:MATRICOLA5974 pubblicazioni:autoreCNRDi prodotto:ID168050 . @prefix modulo: . modulo:ID2449 prodottidellaricerca:prodotto prodotto:ID168050 . modulo:ID2111 prodottidellaricerca:prodotto prodotto:ID168050 . @prefix unitaDiPersonaleEsterno: . unitaDiPersonaleEsterno:ID6208 pubblicazioni:autoreCNRDi prodotto:ID168050 . @prefix rdf: . @prefix retescientifica: . prodotto:ID168050 rdf:type retescientifica:ProdottoDellaRicerca , prodotto:TIPO1101 . @prefix rdfs: . prodotto:ID168050 rdfs:label "Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem (Articolo in rivista)"@en . @prefix xsd: . prodotto:ID168050 pubblicazioni:anno "2005-01-01T00:00:00+01:00"^^xsd:gYear ; pubblicazioni:doi "10.1016/j.cor.2004.03.008"^^xsd:string . @prefix skos: . prodotto:ID168050 skos:altLabel "
Confessore, G. ; Dell'Olmo, P. ; Gentili, M. (2005)
Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem
in Computers & operations research; Pergamon-Elsevier Science Ltd., Oxford (Regno Unito)
"^^rdf:HTML ; pubblicazioni:autori "Confessore, G. ; Dell'Olmo, P. ; Gentili, M."^^xsd:string ; pubblicazioni:paginaInizio "2383"^^xsd:string ; pubblicazioni:paginaFine "2405"^^xsd:string ; pubblicazioni:numeroVolume "32"^^xsd:string . @prefix ns12: . prodotto:ID168050 pubblicazioni:rivista ns12:ID337218 ; pubblicazioni:numeroFascicolo "9"^^xsd:string ; skos:note "ISI Web of Science (WOS)"^^xsd:string , "Scopu"^^xsd:string ; pubblicazioni:affiliazioni "Dell'Olmo,P. Universit\u00E0 Roma la Sapienza;\nGentili, M. Universit\u00E0 di Salerno"^^xsd:string ; pubblicazioni:titolo "Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem"^^xsd:string ; prodottidellaricerca:abstract "Monitoring flows on networks is a research area for which a number of applications are waiting for models and algorithms to face new problems emerging with a very high paced. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this field especially for urban transportation networks. Given an undirected graph G = (V, E) and a subset B subset of V of bound vertices, we look for a set of vertices M of minimum size such that each element of M is the origin of one or more paths, and, the set of all these paths dominates B. For this NP-hard problem, we present an approximation algorithm and new heuristic procedures extensively evaluated on a set of test instances. We defined two different sets of benchmarks: grid graphs and random graphs. Moreover, we included two test cases taken from real traffic networks. Computational results, discussed in the paper, give insights both on the problem and on algorithms' performance."@en . @prefix ns13: . prodotto:ID168050 pubblicazioni:editore ns13:ID9199 ; prodottidellaricerca:prodottoDi istituto:CDS003 , modulo:ID2449 , modulo:ID2111 ; pubblicazioni:autoreCNR unitaDiPersonaleEsterno:ID6208 , unitaDiPersonaleInterno:MATRICOLA5974 . ns12:ID337218 pubblicazioni:rivistaDi prodotto:ID168050 . ns13:ID9199 pubblicazioni:editoreDi prodotto:ID168050 .