Given a graph G, the Minimum Dominating Trail Set (MDTS) problem consists in finding a minimum cardinality collection of pairwise edge-disjoint trails such that each edge of G has at least one endvertex on some trail. The MDTS problem is NP-hard for general graphs. In this paper an algorithmic approach for the MDTS problem on (two-terminal) series parallel graphs is presented.
Detti, P., Meloni, C., Pranzo, M. (2004). Minimum dominating trail set for two-terminal series parallel graphs. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 17(20), 117-122.
Minimum dominating trail set for two-terminal series parallel graphs
DETTI, PAOLO;PRANZO, MARCO
2004-01-01
Abstract
Given a graph G, the Minimum Dominating Trail Set (MDTS) problem consists in finding a minimum cardinality collection of pairwise edge-disjoint trails such that each edge of G has at least one endvertex on some trail. The MDTS problem is NP-hard for general graphs. In this paper an algorithmic approach for the MDTS problem on (two-terminal) series parallel graphs is presented.
| File | Dimensione | Formato | |
|---|---|---|---|
|
SeriesParallel.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
165.03 kB
Formato
Adobe PDF
|
165.03 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/10940
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo