Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem (Articolo in rivista) (literal)

Anno

• 2005-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1016/j.cor.2004.03.008 (literal)

Alternative label

• 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)
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Confessore, G. ; Dell'Olmo, P. ; Gentili, M. (literal)

Pagina inizio

• 2383 (literal)

Pagina fine

• 2405 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 32 (literal)

Rivista

• Computers & operations research (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo

• 9 (literal)

Note

• ISI Web of Science (WOS) (literal)
• Scopu (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Dell'Olmo,P. Università Roma la Sapienza; Gentili, M. Università di Salerno (literal)

Titolo

• Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem (literal)

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. (literal)

Editore

• Pergamon-Elsevier Science Ltd. (Editore)

Prodotto di

• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)
• Metodologie e strumenti per i processi produttivi e logistici nel manifatturiero (SP.P01.017.001) (Modulo)
• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)

Autore CNR

• PAOLO DELL'OLMO (Persona)
• GIUSEPPE CONFESSORE (Unità di personale interno)

Incoming links:

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Metodologie e strumenti per i processi produttivi e logistici nel manifatturiero (SP.P01.017.001) (Modulo)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Autore CNR di

• GIUSEPPE CONFESSORE (Unità di personale interno)
• PAOLO DELL'OLMO (Persona)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Computers & operations research (Rivista)

Editore di

• Pergamon-Elsevier Science Ltd. (Editore)