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.
Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs / Detti, P., Meloni, C., Pranzo, M.. - 17:(2004), pp. 117-122. (Workshop on Graphs and Combinatorial Optimization, CTW04 Menaggio, Italy ) [10.1016/j.endm.2004.03.014].
Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs
Carlo Meloni;
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 allegati a 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.
