Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs

作     者：Detti, Paolo Meloni, Carlo Pranzo, Marco 

作者机构：Dipartimento di Ingegneria dell'Informazione - Università di Siena Italy Dipartimento di Elettrotecnica ed Elettronica - Politecnico di Bari Italy Dipartimento di Informatica Automazione - Università Roma Tre Italy 

出 版 物：《Electronic Notes in Discrete Mathematics》 (Electron. Notes Discrete Math.)

年 卷 期：2004年第17卷

页      面：117-122页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：edge domination graph algorithms series parallel graphs 

摘      要：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. © 2004 Elsevier B.V. All rights reserved.