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 pace. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this filed specially for urban transportation networks. Given an undirected graph G = (V; E) and a subset B ⊆ 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.

Experimental Evaluation of Approximation and Heuristic Algorithms for the Dominating Paths Problem

GENTILI, Monica
2005

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 pace. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this filed specially for urban transportation networks. Given an undirected graph G = (V; E) and a subset B ⊆ 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/1861828
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact