Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Transversals of subtree hypergraphs and the source location problem in digraphs.

van den Heuvel, J. and Johnson, M. (2008) 'Transversals of subtree hypergraphs and the source location problem in digraphs.', Networks., 51 (2). pp. 113-119.

Abstract

A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to find a minimum size transversal in time polynomial in n. In this paper, we show that if it is possible to decide if a set of vertices W ⊆ V is a transversal in time S(n) (where n = |V|), then it is possible to find a minimum size transversal in O(n3S(n)). This result provides a polynomial algorithm for the Source Location Problem: a set of (k,l)-sources for a digraph D = (V,A) is a subset S of V such that for any v ∈ V there are k arc-disjoint paths that each join a vertex of S to v and l arc-disjoint paths that each join v to S. The Source Location Problem is to find a minimum size set of (k,l)-sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case S(n) is polynomial.

Item Type:Article
Keywords:Graphs, Hypergraphs, Source location, Algorithms.
Full text:PDF - Accepted Version (170Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1002/net.20206
Publisher statement:This is the accepted version of the following article: van den Heuvel, J. and Johnson, M. (2008), Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2): 113-119, which has been published in final form at http://dx.doi.org/10.1002/net.20206. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
Record Created:07 Oct 2008
Last Modified:11 Dec 2015 11:23

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library