The present contribution considers the problem of identifying a simple cycle in an undirected graph such that the number of nodes in the cycle or adjacent to it, is maximum. This problem is denoted as the Maximum Covering Cycle Problem (MCCP) and it is shown to be NP–complete. We present an iterative procedure that, although it cannot be shown to be polynomial, yields (in practice) high-quality solutions within reasonable time on graphs of moderate density.
Searching for a cycle with maximum coverage in undirected graphs
GROSSO, Andrea Cesare;
2016-01-01
Abstract
The present contribution considers the problem of identifying a simple cycle in an undirected graph such that the number of nodes in the cycle or adjacent to it, is maximum. This problem is denoted as the Maximum Covering Cycle Problem (MCCP) and it is shown to be NP–complete. We present an iterative procedure that, although it cannot be shown to be polynomial, yields (in practice) high-quality solutions within reasonable time on graphs of moderate density.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
MCCP_OPTL_REV2.pdf
Open Access dal 29/09/2017
Tipo di file:
POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione
250.59 kB
Formato
Adobe PDF
|
250.59 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
