Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

Institution:	1. Freie Universität Berlin, Arnimallee 6, Room 101, 14195 Berlin, Germany;2. Berlin Mathematical School, Berlin, Germany;3. International Max Planck Research School for Computational Biology and Scientific Computing, Max Planck Institute for Molecular Genetics, Ihnestr 63-73, 14195 Berlin, Germany;4. Forschungszentrum Matheon, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany

Abstract:	In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that $\| W \| = k$ , for a fixed positive integer k. The enumeration is performed within $O (n)$ delay, where $n = \| V (G) \|$ consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset $W \subseteq V (G)$ can be computed in polynomial time, provided that the size of W is bounded by a constant.

Keywords:
本文献已被 ScienceDirect 等数据库收录！