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, Paolo; Meloni, Carlo; Pranzo, Marco. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - ELETTRONICO. - 17:(2004), pp. 117-122. (Intervento presentato al convegno Workshop on Graphs and Combinatorial Optimization, CTW04 tenutosi a Menaggio, Italy nel May 31 - June 2, 2004) [10.1016/j.endm.2004.03.014].
Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs
Carlo Meloni;
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
