Embedding complexity and discrete optimization II: A dynamical programming approach to the Steiner-Tree Problem

Cieslik, D., Dress, A., Huber, K. T. and Moulton, V. ORCID: https://orcid.org/0000-0001-9371-6435 (2002) Embedding complexity and discrete optimization II: A dynamical programming approach to the Steiner-Tree Problem. Annals of Combinatorics, 6 (3-4). pp. 275-283. ISSN 0218-0006

Full text not available from this repository. (Request a copy)

Abstract

In this note, we continue our work devoted to investigating the concept of embedding complexity (cf. Cieslik et al. [3]) and present a new Divide and Conquer algorithm for solving the Steiner-tree problem for graphs that relies on dynamic-programming schemes. In this way,we show how the rather general conceptual framework developed in our previous paper can be used even in rather awkward situations and that, more specifically, it allows us to design a treewidthbased algorithm for finding Steiner trees in a (weighted or unweighted) graph that is linear with respect to the number of the graph's vertices, yet (as we cannot avoid paying the "standard fine" set on using treewidth-based algorithms) highly exponential with respect to the graph's treewidth.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Vishal Gautam
Date Deposited:	27 Jul 2011 12:48
Last Modified:	20 Jun 2023 14:43
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23324
DOI:	10.1007/s000260200003

Actions (login required)

View Item