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

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 in questo prodotto:
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.

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

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